祭りの準備作業の余裕時間

import sysfrom collections import deque  def 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()

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(" "));

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(" "));

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);    }}

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);    }}

#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;}

#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;}

첫줄 = コンソール.数読み();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.つなぐ(" "));