축제를 준비하는 일이 n개 있고 1번부터 n번까지 번호가 있다.
i번 일은 d_i분이 걸리고, 재료가 r_i분에 도착하므로 r_i분보다 먼저 시작할 수 없다.
조건 m개가 주어지며, 조건 "a b"는 a번 일이 끝난 뒤에야(끝나는 바로 그 시각부터) b번 일을 시작할 수 있다는 뜻이다.
같은 조건이 여러 번 주어질 수 있고, 조건을 따라가서 제자리로 돌아오는 일은 없다.
일손은 넉넉해서 여러 일을 동시에 할 수 있고, 시작한 일은 쉬지 않고 끝낸다.
i번 일의 가장 이른 시작 시각 E_i는, r_i와 'i번 일보다 먼저 끝나야 하는 일 j들의 E_j + d_j' 가운데 가장 큰 값이다.
전체 끝 시각 T는 모든 일의 E_i + d_i 가운데 가장 큰 값이다.
i번 일의 가장 늦은 끝 시각 F_i는, i번 일이 끝나야 시작할 수 있는 일 j가 하나도 없으면 T이고, 있으면 그런 일 j들의 F_j - d_j 가운데 가장 작은 값이다.
i번 일의 여유 시간은 F_i - d_i - E_i이다(전체 끝 시각을 늦추지 않고 그 일의 시작을 미룰 수 있는 시간).
예제에서는 3번 일의 재료가 5분에 도착하므로 E_3 = 5, E_4 = 9이고 T = 10이다. F_4 = 10, F_2 = F_3 = 9이고 F_1은 9 - 2와 9 - 4 가운데 작은 값인 5이므로, 1번 일의 여유 시간은 5 - 3 - 0 = 2이다.
T와 모든 일의 여유 시간을 구하라.
입력
첫 줄에 n과 m이 빈칸으로 나뉘어 주어진다. 둘째 줄에 d_1부터 d_n까지, 셋째 줄에 r_1부터 r_n까지 빈칸 하나로 나뉘어 주어진다. 다음 m줄에 조건 "a b"가 한 줄에 하나씩 주어진다. 1 ≤ n ≤ 5,000, 0 ≤ m ≤ 10,000, 1 ≤ d_i ≤ 1,000,000,000, 0 ≤ r_i ≤ 1,000,000,000, 1 ≤ a, b ≤ n, a ≠ b
출력
첫 줄에 T. 둘째 줄에 1번 일부터 n번 일까지의 여유 시간을 빈칸 하나로 띄워 출력한다. 수는 쉼표 없이 숫자만 쓴다
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
위상 정렬을 두 번 써요. 앞으로 한 번(먼저 할 일이 다 정해진 일부터 꺼내며 가장 이른 시작을 민다), 그리고 그 꺼낸 차례를 거꾸로 한 번(가장 늦은 끝을 당긴다). 그래서 큐를 따로 두지 않고 '꺼낸 차례 목록'에 뒤로 넣고 앞에서부터 읽으면 큐와 차례 기록을 한꺼번에 얻어요. 큐를 쓴다면 Python collections.deque(list.pop(0)은 뒤 칸을 모두 당겨서 느려요), Java ArrayDeque, C# Queue<T>, C++ std::queue, JS·TS·C·크레이콘은 목록과 '머리 번호'로 해요. 함정 하나: 시각이 32비트를 넘어요. 10억 분짜리 일 5,000개가 한 줄로 이어지면 끝 시각이 5조예요. Java·C#의 int는 오류 없이 돌아서 엉뚱한 수가 되고 C·C++은 정의되지 않은 동작이니 long·long long을 써요. Python 정수는 한계가 없고 JS·TS·크레이콘의 수는 2^53(약 9천조)까지 정확해서 그대로 돼요. 함정 둘: 조건은 번호가 큰 일에서 작은 일로도 걸려요. 1번부터 번호 차례로 계산하면 아직 정해지지 않은 값을 쓰게 돼요. 차례는 번호가 아니라 '남은 선행 조건 수가 0이 된 차례'예요. 함정 셋: 같은 조건이 두 번 나올 때 한쪽만 합치면 안 돼요. 뒤따르는 일을 집합(Set)에 넣어 하나로 합쳤다면 선행 조건 수도 한 번만 세야 해요. 줄마다 세면 그 수가 0이 되지 않아 그 일과 뒤의 일이 영영 큐에 들어가지 못해요. 목록에 두 번 넣고 두 번 세는 쪽이 간단해요. 함정 넷: 뒤따르는 일이 없는 일의 가장 늦은 끝은 제 끝 시각이 아니라 전체 끝 시각 T예요. 일찍 끝나는 곁가지 일에도 여유가 있어요. 함정 다섯: 가장 이른 시작은 0이 아니라 재료 도착 시각 r_i에서 출발해요. 그래서 가장 긴 사슬 위에 있는 일에도 여유가 생길 수 있어요(예제의 1번 일). 크레이콘은 콘솔.수들읽기()로 한 줄의 수를 목록으로 받고 새목록(n, total)로 채운 목록을 만들어요.
Pythonmain.py · 47 줄
import sysfrom collections import dequedef main(): data = sys.stdin.buffer.read().split() n, m = int(data[0]), int(data[1]) d = [0] + [int(x) for x in data[2 : 2 + n]] start = [0] + [int(x) for x in data[2 + n : 2 + 2 * n]] # 가장 이른 시작(처음에는 재료 도착 시각) nxt = [[] for _ in range(n + 1)] indeg = [0] * (n + 1) pos = 2 + 2 * n for _ in range(m): a, b = int(data[pos]), int(data[pos + 1]) pos += 2 nxt[a].append(b) # 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b] += 1 # 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 order = [] queue = deque(i for i in range(1, n + 1) if indeg[i] == 0) while queue: a = queue.popleft() order.append(a) finish = start[a] + d[a] for b in nxt[a]: if finish > start[b]: start[b] = finish indeg[b] -= 1 if indeg[b] == 0: queue.append(b) total = max(start[i] + d[i] for i in range(1, n + 1)) # 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) late = [total] * (n + 1) for a in reversed(order): for b in nxt[a]: if late[b] - d[b] < late[a]: late[a] = late[b] - d[b] print(total) print(" ".join(str(late[i] - d[i] - start[i]) for i in range(1, n + 1)))main()
JavaScriptmain.js · 44 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);const n = data[0];const m = data[1];const d = [0];const start = [0]; // 가장 이른 시작(처음에는 재료 도착 시각)for (let i = 0; i < n; i++) { d.push(data[2 + i]); start.push(data[2 + n + i]);}const next = Array.from({ length: n + 1 }, () => []);const indeg = new Array(n + 1).fill(0);for (let e = 0; e < m; e++) { const a = data[2 + 2 * n + 2 * e]; const b = data[3 + 2 * n + 2 * e]; next[a].push(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++;}// 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다const order = [];for (let i = 1; i <= n; i++) if (indeg[i] === 0) order.push(i);for (let head = 0; head < order.length; head++) { const a = order[head]; const finish = start[a] + d[a]; for (const b of next[a]) { if (finish > start[b]) start[b] = finish; if (--indeg[b] === 0) order.push(b); }}let total = 0;for (let i = 1; i <= n; i++) total = Math.max(total, start[i] + d[i]);// 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total)const late = new Array(n + 1).fill(total);for (let k = order.length - 1; k >= 0; k--) { const a = order[k]; for (const b of next[a]) late[a] = Math.min(late[a], late[b] - d[b]);}const slack = [];for (let i = 1; i <= n; i++) slack.push(late[i] - d[i] - start[i]);console.log(total + "\n" + slack.join(" "));
TypeScriptmain.ts · 46 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);const n = data[0];const m = data[1];const d: number[] = [0];const start: number[] = [0]; // 가장 이른 시작(처음에는 재료 도착 시각)for (let i = 0; i < n; i++) { d.push(data[2 + i]); start.push(data[2 + n + i]);}const next: number[][] = Array.from({ length: n + 1 }, (): number[] => []);const indeg: number[] = new Array<number>(n + 1).fill(0);for (let e = 0; e < m; e++) { const a = data[2 + 2 * n + 2 * e]; const b = data[3 + 2 * n + 2 * e]; next[a].push(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++;}// 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다const order: number[] = [];for (let i = 1; i <= n; i++) if (indeg[i] === 0) order.push(i);for (let head = 0; head < order.length; head++) { const a = order[head]; const finish = start[a] + d[a]; for (const b of next[a]) { if (finish > start[b]) start[b] = finish; if (--indeg[b] === 0) order.push(b); }}let total = 0;for (let i = 1; i <= n; i++) total = Math.max(total, start[i] + d[i]);// 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total)const late: number[] = new Array<number>(n + 1).fill(total);for (let k = order.length - 1; k >= 0; k--) { const a = order[k]; for (const b of next[a]) late[a] = Math.min(late[a], late[b] - d[b]);}const slack: number[] = [];for (let i = 1; i <= n; i++) slack.push(late[i] - d[i] - start[i]);console.log(total + "\n" + slack.join(" "));
JavaMain.java · 67 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); // 시각은 10^9을 여러 번 더하므로 long이어야 한다 long[] d = new long[n + 1]; long[] start = new long[n + 1]; // 가장 이른 시작(처음에는 재료 도착 시각) st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) d[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) start[i] = Long.parseLong(st.nextToken()); List<List<Integer>> next = new ArrayList<>(); for (int i = 0; i <= n; i++) next.add(new ArrayList<>()); int[] indeg = new int[n + 1]; for (int e = 0; e < m; e++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); next.get(a).add(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++; } // 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 int[] order = new int[n]; int tail = 0; for (int i = 1; i <= n; i++) if (indeg[i] == 0) order[tail++] = i; for (int head = 0; head < tail; head++) { int a = order[head]; long finish = start[a] + d[a]; for (int b : next.get(a)) { if (finish > start[b]) start[b] = finish; if (--indeg[b] == 0) order[tail++] = b; } } long total = 0; for (int i = 1; i <= n; i++) total = Math.max(total, start[i] + d[i]); // 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) long[] late = new long[n + 1]; Arrays.fill(late, total); for (int k = tail - 1; k >= 0; k--) { int a = order[k]; for (int b : next.get(a)) late[a] = Math.min(late[a], late[b] - d[b]); } StringBuilder sb = new StringBuilder(); sb.append(total).append('\n'); for (int i = 1; i <= n; i++) { if (i > 1) sb.append(' '); sb.append(late[i] - d[i] - start[i]); } System.out.println(sb); }}
C#Main.cs · 69 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]); int m = int.Parse(t[1]); // 시각은 10^9을 여러 번 더하므로 long이어야 한다 long[] d = new long[n + 1]; long[] start = new long[n + 1]; // 가장 이른 시작(처음에는 재료 도착 시각) for (int i = 1; i <= n; i++) { d[i] = long.Parse(t[1 + i]); start[i] = long.Parse(t[1 + n + i]); } var next = new List<int>[n + 1]; for (int i = 0; i <= n; i++) next[i] = new List<int>(); int[] indeg = new int[n + 1]; for (int e = 0; e < m; e++) { int a = int.Parse(t[2 + 2 * n + 2 * e]); int b = int.Parse(t[3 + 2 * n + 2 * e]); next[a].Add(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++; } // 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 int[] order = new int[n]; int tail = 0; for (int i = 1; i <= n; i++) if (indeg[i] == 0) order[tail++] = i; for (int head = 0; head < tail; head++) { int a = order[head]; long finish = start[a] + d[a]; foreach (int b in next[a]) { if (finish > start[b]) start[b] = finish; if (--indeg[b] == 0) order[tail++] = b; } } long total = 0; for (int i = 1; i <= n; i++) total = Math.Max(total, start[i] + d[i]); // 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) long[] late = new long[n + 1]; Array.Fill(late, total); for (int k = tail - 1; k >= 0; k--) { int a = order[k]; foreach (int b in next[a]) late[a] = Math.Min(late[a], late[b] - d[b]); } var sb = new StringBuilder(); sb.Append(total).Append('\n'); for (int i = 1; i <= n; i++) { if (i > 1) sb.Append(' '); sb.Append(late[i] - d[i] - start[i]); } Console.WriteLine(sb); }}
C++main.cpp · 56 줄
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; // 시각은 10^9을 여러 번 더하므로 long long이어야 한다 vector<long long> d(n + 1), start(n + 1); // start: 가장 이른 시작(처음에는 재료 도착 시각) for (int i = 1; i <= n; i++) cin >> d[i]; for (int i = 1; i <= n; i++) cin >> start[i]; vector<vector<int>> next(n + 1); vector<int> indeg(n + 1, 0); for (int e = 0; e < m; e++) { int a, b; cin >> a >> b; next[a].push_back(b); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[b]++; } // 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 vector<int> order; order.reserve(n); for (int i = 1; i <= n; i++) if (indeg[i] == 0) order.push_back(i); for (size_t head = 0; head < order.size(); head++) { int a = order[head]; long long finish = start[a] + d[a]; for (int b : next[a]) { start[b] = max(start[b], finish); if (--indeg[b] == 0) order.push_back(b); } } long long total = 0; for (int i = 1; i <= n; i++) total = max(total, start[i] + d[i]); // 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) vector<long long> late(n + 1, total); for (int k = (int)order.size() - 1; k >= 0; k--) { int a = order[k]; for (int b : next[a]) late[a] = min(late[a], late[b] - d[b]); } cout << total << '\n'; for (int i = 1; i <= n; i++) { if (i > 1) cout << ' '; cout << late[i] - d[i] - start[i]; } cout << '\n'; return 0;}
Cmain.c · 67 줄
#include <stdio.h>#include <stdlib.h>int main(void) { int n, m; if (scanf("%d %d", &n, &m) != 2) return 1; // 시각은 10^9을 여러 번 더하므로 long long이어야 한다 long long *d = malloc(sizeof(long long) * (n + 1)); long long *start = malloc(sizeof(long long) * (n + 1)); // 가장 이른 시작 long long *late = malloc(sizeof(long long) * (n + 1)); // 가장 늦은 끝 for (int i = 1; i <= n; i++) scanf("%lld", &d[i]); for (int i = 1; i <= n; i++) scanf("%lld", &start[i]); // 인접 목록: head[a]에서 시작해 nxt[e]를 따라가면 a 뒤에 오는 일이 차례로 나온다 int *head = malloc(sizeof(int) * (n + 1)); int *to = malloc(sizeof(int) * (m + 1)); int *nxt = malloc(sizeof(int) * (m + 1)); int *indeg = calloc(n + 1, sizeof(int)); for (int i = 0; i <= n; i++) head[i] = -1; for (int e = 0; e < m; e++) { int a, b; scanf("%d %d", &a, &b); to[e] = b; // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 nxt[e] = head[a]; head[a] = e; indeg[b]++; } // 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다 int *order = malloc(sizeof(int) * (n + 1)); int tail = 0; for (int i = 1; i <= n; i++) if (indeg[i] == 0) order[tail++] = i; for (int h = 0; h < tail; h++) { int a = order[h]; long long finish = start[a] + d[a]; for (int e = head[a]; e != -1; e = nxt[e]) { int b = to[e]; if (finish > start[b]) start[b] = finish; if (--indeg[b] == 0) order[tail++] = b; } } long long total = 0; for (int i = 1; i <= n; i++) { if (start[i] + d[i] > total) total = start[i] + d[i]; } // 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total) for (int i = 1; i <= n; i++) late[i] = total; for (int k = tail - 1; k >= 0; k--) { int a = order[k]; for (int e = head[a]; e != -1; e = nxt[e]) { int b = to[e]; if (late[b] - d[b] < late[a]) late[a] = late[b] - d[b]; } } printf("%lld\n", total); for (int i = 1; i <= n; i++) { printf(i > 1 ? " %lld" : "%lld", late[i] - d[i] - start[i]); } printf("\n"); free(d); free(start); free(late); free(head); free(to); free(nxt); free(indeg); free(order); return 0;}
Craykonmain.cray · 70 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];d = 콘솔.수들읽기(); // d[i - 1]: i번 일에 걸리는 시간start = 콘솔.수들읽기(); // 가장 이른 시작(처음에는 재료 도착 시각)next = [];indeg = 새목록(n, 0);반복 (i = 0; i < n; i++){ next.넣기([]);}반복 (e = 0; e < m; e++){ ab = 콘솔.수들읽기(); next[ab[0] - 1].넣기(ab[1] - 1); // 같은 조건이 두 번 나오면 두 번 넣고 두 번 센다 indeg[ab[1] - 1] += 1;}// 앞으로: 먼저 할 일이 모두 정해진 일부터 꺼내며 가장 이른 시작을 민다order = [];반복 (i = 0; i < n; i++){ 만약 (indeg[i] == 0) { order.넣기(i); }}반복 (head = 0; head < order.개수; head++){ a = order[head]; finish = start[a] + d[a]; 각각 (b 에서 next[a]) { 만약 (finish > start[b]) { start[b] = finish; } indeg[b] -= 1; 만약 (indeg[b] == 0) { order.넣기(b); } }}total = 0;반복 (i = 0; i < n; i++){ total = 수학.큰수(total, start[i] + d[i]);}// 뒤로: 꺼낸 차례를 거꾸로 돌며 가장 늦은 끝을 당긴다(뒤따르는 일이 없으면 total)late = 새목록(n, total);반복 (k = order.개수 - 1; k >= 0; k--){ a = order[k]; 각각 (b 에서 next[a]) { late[a] = 수학.작은수(late[a], late[b] - d[b]); }}slack = [];반복 (i = 0; i < n; i++){ slack.넣기(late[i] - d[i] - start[i]);}콘솔.쓰기(total);콘솔.쓰기(slack.잇기(" "));