Submission #164303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
164303	2019-11-19T06:03:33 Z	fluffypotato	Art Exhibition (JOI18_art)	Java 11	50 / 100	1000 ms	102228 KB

art

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

public class art {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        int n=Integer.parseInt(f.readLine());
        long ans=0;

        ArrayList<pair>arr=new ArrayList<>();
        for(int i=0;i<n;i++){
            StringTokenizer st=new StringTokenizer(f.readLine());
            long a=Long.parseLong(st.nextToken());
            long b=Long.parseLong(st.nextToken());
            ans=Math.max(ans,b);
            arr.add(new pair(a,b));
        }
        Collections.sort(arr);
        long best=0;
        long pfx=0;
        long lastpfx=0;
        for(int i=0;i<n;i++){
            pfx+=arr.get(i).val;
            ans=Math.max(pfx-arr.get(i).size+best,ans);
            best=Math.max(best,-lastpfx+arr.get(i).size);
            lastpfx=pfx;
        }
        System.out.print(ans);

        f.close();
        out.close();
    }
}class pair implements Comparable <pair>{
    long size;
    long val;

    public int compareTo(pair other){
        if(size>other.size)return 1;
        return -1;
    }


    pair(long a, long b)
    {
        size=a;
        val=b;
    }
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	9844 KB	Output is correct
2	Correct	121 ms	9772 KB	Output is correct
3	Correct	91 ms	9928 KB	Output is correct
4	Correct	89 ms	9700 KB	Output is correct
5	Correct	90 ms	9612 KB	Output is correct
6	Correct	90 ms	9824 KB	Output is correct
7	Correct	93 ms	9696 KB	Output is correct
8	Correct	91 ms	9956 KB	Output is correct
9	Correct	92 ms	9556 KB	Output is correct
10	Correct	89 ms	9816 KB	Output is correct
11	Correct	88 ms	9828 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	9844 KB	Output is correct
2	Correct	121 ms	9772 KB	Output is correct
3	Correct	91 ms	9928 KB	Output is correct
4	Correct	89 ms	9700 KB	Output is correct
5	Correct	90 ms	9612 KB	Output is correct
6	Correct	90 ms	9824 KB	Output is correct
7	Correct	93 ms	9696 KB	Output is correct
8	Correct	91 ms	9956 KB	Output is correct
9	Correct	92 ms	9556 KB	Output is correct
10	Correct	89 ms	9816 KB	Output is correct
11	Correct	88 ms	9828 KB	Output is correct
12	Correct	107 ms	10256 KB	Output is correct
13	Correct	107 ms	10436 KB	Output is correct
14	Correct	126 ms	10588 KB	Output is correct
15	Correct	109 ms	10592 KB	Output is correct
16	Correct	106 ms	10644 KB	Output is correct
17	Correct	106 ms	10412 KB	Output is correct
18	Correct	109 ms	10492 KB	Output is correct
19	Correct	104 ms	10672 KB	Output is correct
20	Correct	104 ms	10592 KB	Output is correct
21	Correct	104 ms	10760 KB	Output is correct
22	Correct	105 ms	10636 KB	Output is correct
23	Correct	105 ms	10676 KB	Output is correct
24	Correct	115 ms	10780 KB	Output is correct
25	Correct	107 ms	10392 KB	Output is correct
26	Correct	108 ms	10648 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	9844 KB	Output is correct
2	Correct	121 ms	9772 KB	Output is correct
3	Correct	91 ms	9928 KB	Output is correct
4	Correct	89 ms	9700 KB	Output is correct
5	Correct	90 ms	9612 KB	Output is correct
6	Correct	90 ms	9824 KB	Output is correct
7	Correct	93 ms	9696 KB	Output is correct
8	Correct	91 ms	9956 KB	Output is correct
9	Correct	92 ms	9556 KB	Output is correct
10	Correct	89 ms	9816 KB	Output is correct
11	Correct	88 ms	9828 KB	Output is correct
12	Correct	107 ms	10256 KB	Output is correct
13	Correct	107 ms	10436 KB	Output is correct
14	Correct	126 ms	10588 KB	Output is correct
15	Correct	109 ms	10592 KB	Output is correct
16	Correct	106 ms	10644 KB	Output is correct
17	Correct	106 ms	10412 KB	Output is correct
18	Correct	109 ms	10492 KB	Output is correct
19	Correct	104 ms	10672 KB	Output is correct
20	Correct	104 ms	10592 KB	Output is correct
21	Correct	104 ms	10760 KB	Output is correct
22	Correct	105 ms	10636 KB	Output is correct
23	Correct	105 ms	10676 KB	Output is correct
24	Correct	115 ms	10780 KB	Output is correct
25	Correct	107 ms	10392 KB	Output is correct
26	Correct	108 ms	10648 KB	Output is correct
27	Correct	198 ms	15092 KB	Output is correct
28	Correct	198 ms	15436 KB	Output is correct
29	Correct	237 ms	15504 KB	Output is correct
30	Correct	202 ms	15264 KB	Output is correct
31	Correct	202 ms	15420 KB	Output is correct
32	Correct	204 ms	15512 KB	Output is correct
33	Correct	204 ms	15408 KB	Output is correct
34	Correct	230 ms	15656 KB	Output is correct
35	Correct	191 ms	15440 KB	Output is correct
36	Correct	198 ms	15228 KB	Output is correct
37	Correct	194 ms	15108 KB	Output is correct
38	Correct	220 ms	15600 KB	Output is correct
39	Correct	265 ms	15616 KB	Output is correct
40	Correct	202 ms	15124 KB	Output is correct
41	Correct	234 ms	15396 KB	Output is correct
42	Correct	215 ms	15620 KB	Output is correct
43	Correct	217 ms	15848 KB	Output is correct
44	Correct	207 ms	15368 KB	Output is correct
45	Correct	192 ms	15256 KB	Output is correct
46	Correct	207 ms	15584 KB	Output is correct
47	Correct	228 ms	15088 KB	Output is correct
48	Correct	201 ms	15448 KB	Output is correct
49	Correct	193 ms	15216 KB	Output is correct
50	Correct	201 ms	15316 KB	Output is correct
51	Correct	197 ms	15268 KB	Output is correct

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	9844 KB	Output is correct
2	Correct	121 ms	9772 KB	Output is correct
3	Correct	91 ms	9928 KB	Output is correct
4	Correct	89 ms	9700 KB	Output is correct
5	Correct	90 ms	9612 KB	Output is correct
6	Correct	90 ms	9824 KB	Output is correct
7	Correct	93 ms	9696 KB	Output is correct
8	Correct	91 ms	9956 KB	Output is correct
9	Correct	92 ms	9556 KB	Output is correct
10	Correct	89 ms	9816 KB	Output is correct
11	Correct	88 ms	9828 KB	Output is correct
12	Correct	107 ms	10256 KB	Output is correct
13	Correct	107 ms	10436 KB	Output is correct
14	Correct	126 ms	10588 KB	Output is correct
15	Correct	109 ms	10592 KB	Output is correct
16	Correct	106 ms	10644 KB	Output is correct
17	Correct	106 ms	10412 KB	Output is correct
18	Correct	109 ms	10492 KB	Output is correct
19	Correct	104 ms	10672 KB	Output is correct
20	Correct	104 ms	10592 KB	Output is correct
21	Correct	104 ms	10760 KB	Output is correct
22	Correct	105 ms	10636 KB	Output is correct
23	Correct	105 ms	10676 KB	Output is correct
24	Correct	115 ms	10780 KB	Output is correct
25	Correct	107 ms	10392 KB	Output is correct
26	Correct	108 ms	10648 KB	Output is correct
27	Correct	198 ms	15092 KB	Output is correct
28	Correct	198 ms	15436 KB	Output is correct
29	Correct	237 ms	15504 KB	Output is correct
30	Correct	202 ms	15264 KB	Output is correct
31	Correct	202 ms	15420 KB	Output is correct
32	Correct	204 ms	15512 KB	Output is correct
33	Correct	204 ms	15408 KB	Output is correct
34	Correct	230 ms	15656 KB	Output is correct
35	Correct	191 ms	15440 KB	Output is correct
36	Correct	198 ms	15228 KB	Output is correct
37	Correct	194 ms	15108 KB	Output is correct
38	Correct	220 ms	15600 KB	Output is correct
39	Correct	265 ms	15616 KB	Output is correct
40	Correct	202 ms	15124 KB	Output is correct
41	Correct	234 ms	15396 KB	Output is correct
42	Correct	215 ms	15620 KB	Output is correct
43	Correct	217 ms	15848 KB	Output is correct
44	Correct	207 ms	15368 KB	Output is correct
45	Correct	192 ms	15256 KB	Output is correct
46	Correct	207 ms	15584 KB	Output is correct
47	Correct	228 ms	15088 KB	Output is correct
48	Correct	201 ms	15448 KB	Output is correct
49	Correct	193 ms	15216 KB	Output is correct
50	Correct	201 ms	15316 KB	Output is correct
51	Correct	197 ms	15268 KB	Output is correct
52	Execution timed out	1022 ms	102228 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-