답안 #1022612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022612	2024-07-13T19:22:56 Z	idante	Art Exhibition (JOI18_art)	Java 11	100 / 100	949 ms	109128 KB

art

import java.io.*;
import java.util.*;

public class art {

  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

    long n = Long.parseLong(r.readLine());
    List<Artwork> a = new ArrayList<>();
    for (long i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(r.readLine());

      long x = Long.parseLong(st.nextToken());
      long y = Long.parseLong(st.nextToken());
      a.add(new Artwork(x, y));
    }

    // sort based off of size of the artworks
    a.sort(Comparator.comparingLong(artwork -> artwork.size));

    // prefix sum list
    List<Long> p = new ArrayList<>(Collections.nCopies((int) n, 0L));

    p.set(0, a.get(0).value);
    for (int i = 1; i < n; i++) {
      // update the prefix sum
      p.set(i, p.get(i - 1) + a.get(i).value);
    }

    long cur;
    long res = 0;

    // holds differences between prefix sums
    TreeSet<Long> m = new TreeSet<>();
    for (int i = (int) n - 1; i >= 0; i--) {
      // sum of all up to i - current size
      // i is the largest (A.max)
      m.add(p.get(i) - a.get(i).size);

      // get the maximum difference so far
      cur = m.last() - (i > 0 ? p.get(i - 1) : 0);

      // finish the expression
      cur += a.get(i).size;

      // are we larger?
      res = Math.max(res, cur);
    }
    System.out.println(res);
  }

  static class Artwork {

    long size, value;

    Artwork(long size, long value) {
      this.size = size;
      this.value = value;
    }
  }
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	17016 KB	Output is correct
2	Correct	57 ms	16664 KB	Output is correct
3	Correct	55 ms	15192 KB	Output is correct
4	Correct	58 ms	16576 KB	Output is correct
5	Correct	56 ms	16232 KB	Output is correct
6	Correct	54 ms	14624 KB	Output is correct
7	Correct	55 ms	14724 KB	Output is correct
8	Correct	56 ms	14456 KB	Output is correct
9	Correct	55 ms	16708 KB	Output is correct
10	Correct	55 ms	15008 KB	Output is correct
11	Correct	56 ms	14964 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	17016 KB	Output is correct
2	Correct	57 ms	16664 KB	Output is correct
3	Correct	55 ms	15192 KB	Output is correct
4	Correct	58 ms	16576 KB	Output is correct
5	Correct	56 ms	16232 KB	Output is correct
6	Correct	54 ms	14624 KB	Output is correct
7	Correct	55 ms	14724 KB	Output is correct
8	Correct	56 ms	14456 KB	Output is correct
9	Correct	55 ms	16708 KB	Output is correct
10	Correct	55 ms	15008 KB	Output is correct
11	Correct	56 ms	14964 KB	Output is correct
12	Correct	67 ms	15096 KB	Output is correct
13	Correct	71 ms	16352 KB	Output is correct
14	Correct	71 ms	14368 KB	Output is correct
15	Correct	71 ms	16612 KB	Output is correct
16	Correct	67 ms	15116 KB	Output is correct
17	Correct	74 ms	14316 KB	Output is correct
18	Correct	73 ms	14156 KB	Output is correct
19	Correct	69 ms	14768 KB	Output is correct
20	Correct	73 ms	14912 KB	Output is correct
21	Correct	67 ms	14544 KB	Output is correct
22	Correct	68 ms	14640 KB	Output is correct
23	Correct	69 ms	16808 KB	Output is correct
24	Correct	69 ms	15076 KB	Output is correct
25	Correct	68 ms	14672 KB	Output is correct
26	Correct	67 ms	16856 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	17016 KB	Output is correct
2	Correct	57 ms	16664 KB	Output is correct
3	Correct	55 ms	15192 KB	Output is correct
4	Correct	58 ms	16576 KB	Output is correct
5	Correct	56 ms	16232 KB	Output is correct
6	Correct	54 ms	14624 KB	Output is correct
7	Correct	55 ms	14724 KB	Output is correct
8	Correct	56 ms	14456 KB	Output is correct
9	Correct	55 ms	16708 KB	Output is correct
10	Correct	55 ms	15008 KB	Output is correct
11	Correct	56 ms	14964 KB	Output is correct
12	Correct	67 ms	15096 KB	Output is correct
13	Correct	71 ms	16352 KB	Output is correct
14	Correct	71 ms	14368 KB	Output is correct
15	Correct	71 ms	16612 KB	Output is correct
16	Correct	67 ms	15116 KB	Output is correct
17	Correct	74 ms	14316 KB	Output is correct
18	Correct	73 ms	14156 KB	Output is correct
19	Correct	69 ms	14768 KB	Output is correct
20	Correct	73 ms	14912 KB	Output is correct
21	Correct	67 ms	14544 KB	Output is correct
22	Correct	68 ms	14640 KB	Output is correct
23	Correct	69 ms	16808 KB	Output is correct
24	Correct	69 ms	15076 KB	Output is correct
25	Correct	68 ms	14672 KB	Output is correct
26	Correct	67 ms	16856 KB	Output is correct
27	Correct	241 ms	19516 KB	Output is correct
28	Correct	233 ms	20944 KB	Output is correct
29	Correct	235 ms	18972 KB	Output is correct
30	Correct	247 ms	21144 KB	Output is correct
31	Correct	226 ms	18888 KB	Output is correct
32	Correct	226 ms	18832 KB	Output is correct
33	Correct	260 ms	18956 KB	Output is correct
34	Correct	237 ms	20796 KB	Output is correct
35	Correct	234 ms	21708 KB	Output is correct
36	Correct	254 ms	21368 KB	Output is correct
37	Correct	237 ms	21192 KB	Output is correct
38	Correct	228 ms	19424 KB	Output is correct
39	Correct	240 ms	21372 KB	Output is correct
40	Correct	228 ms	21288 KB	Output is correct
41	Correct	245 ms	19136 KB	Output is correct
42	Correct	240 ms	20940 KB	Output is correct
43	Correct	275 ms	18912 KB	Output is correct
44	Correct	232 ms	21320 KB	Output is correct
45	Correct	224 ms	21672 KB	Output is correct
46	Correct	271 ms	19276 KB	Output is correct
47	Correct	256 ms	18884 KB	Output is correct
48	Correct	237 ms	18992 KB	Output is correct
49	Correct	243 ms	18984 KB	Output is correct
50	Correct	260 ms	18792 KB	Output is correct
51	Correct	233 ms	18808 KB	Output is correct

Subtask #4

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	17016 KB	Output is correct
2	Correct	57 ms	16664 KB	Output is correct
3	Correct	55 ms	15192 KB	Output is correct
4	Correct	58 ms	16576 KB	Output is correct
5	Correct	56 ms	16232 KB	Output is correct
6	Correct	54 ms	14624 KB	Output is correct
7	Correct	55 ms	14724 KB	Output is correct
8	Correct	56 ms	14456 KB	Output is correct
9	Correct	55 ms	16708 KB	Output is correct
10	Correct	55 ms	15008 KB	Output is correct
11	Correct	56 ms	14964 KB	Output is correct
12	Correct	67 ms	15096 KB	Output is correct
13	Correct	71 ms	16352 KB	Output is correct
14	Correct	71 ms	14368 KB	Output is correct
15	Correct	71 ms	16612 KB	Output is correct
16	Correct	67 ms	15116 KB	Output is correct
17	Correct	74 ms	14316 KB	Output is correct
18	Correct	73 ms	14156 KB	Output is correct
19	Correct	69 ms	14768 KB	Output is correct
20	Correct	73 ms	14912 KB	Output is correct
21	Correct	67 ms	14544 KB	Output is correct
22	Correct	68 ms	14640 KB	Output is correct
23	Correct	69 ms	16808 KB	Output is correct
24	Correct	69 ms	15076 KB	Output is correct
25	Correct	68 ms	14672 KB	Output is correct
26	Correct	67 ms	16856 KB	Output is correct
27	Correct	241 ms	19516 KB	Output is correct
28	Correct	233 ms	20944 KB	Output is correct
29	Correct	235 ms	18972 KB	Output is correct
30	Correct	247 ms	21144 KB	Output is correct
31	Correct	226 ms	18888 KB	Output is correct
32	Correct	226 ms	18832 KB	Output is correct
33	Correct	260 ms	18956 KB	Output is correct
34	Correct	237 ms	20796 KB	Output is correct
35	Correct	234 ms	21708 KB	Output is correct
36	Correct	254 ms	21368 KB	Output is correct
37	Correct	237 ms	21192 KB	Output is correct
38	Correct	228 ms	19424 KB	Output is correct
39	Correct	240 ms	21372 KB	Output is correct
40	Correct	228 ms	21288 KB	Output is correct
41	Correct	245 ms	19136 KB	Output is correct
42	Correct	240 ms	20940 KB	Output is correct
43	Correct	275 ms	18912 KB	Output is correct
44	Correct	232 ms	21320 KB	Output is correct
45	Correct	224 ms	21672 KB	Output is correct
46	Correct	271 ms	19276 KB	Output is correct
47	Correct	256 ms	18884 KB	Output is correct
48	Correct	237 ms	18992 KB	Output is correct
49	Correct	243 ms	18984 KB	Output is correct
50	Correct	260 ms	18792 KB	Output is correct
51	Correct	233 ms	18808 KB	Output is correct
52	Correct	936 ms	107180 KB	Output is correct
53	Correct	828 ms	97876 KB	Output is correct
54	Correct	911 ms	100020 KB	Output is correct
55	Correct	895 ms	98280 KB	Output is correct
56	Correct	929 ms	97944 KB	Output is correct
57	Correct	940 ms	98632 KB	Output is correct
58	Correct	891 ms	99972 KB	Output is correct
59	Correct	890 ms	98636 KB	Output is correct
60	Correct	923 ms	98460 KB	Output is correct
61	Correct	949 ms	109128 KB	Output is correct
62	Correct	859 ms	97828 KB	Output is correct
63	Correct	891 ms	98108 KB	Output is correct
64	Correct	819 ms	99400 KB	Output is correct
65	Correct	847 ms	99868 KB	Output is correct
66	Correct	860 ms	98060 KB	Output is correct
67	Correct	846 ms	97656 KB	Output is correct
68	Correct	868 ms	98016 KB	Output is correct