Submission #164304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
164304	2019-11-19T06:06:38 Z	fluffypotato	Art Exhibition (JOI18_art)	Java 11	50 / 100	1000 ms	115732 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;

        pair[]arr=new pair[n];
        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[i]=new pair(a,b);
        }
        Arrays.sort(arr);
        long best=0;
        long pfx=0;
        long lastpfx=0;
        for(int i=0;i<n;i++){
            pfx+=arr[i].val;
            ans=Math.max(pfx-arr[i].size+best,ans);
            best=Math.max(best,-lastpfx+arr[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	94 ms	9960 KB	Output is correct
2	Correct	91 ms	9888 KB	Output is correct
3	Correct	89 ms	9752 KB	Output is correct
4	Correct	93 ms	9700 KB	Output is correct
5	Correct	91 ms	9496 KB	Output is correct
6	Correct	91 ms	9852 KB	Output is correct
7	Correct	92 ms	9796 KB	Output is correct
8	Correct	91 ms	9732 KB	Output is correct
9	Correct	91 ms	9708 KB	Output is correct
10	Correct	89 ms	9640 KB	Output is correct
11	Correct	91 ms	9612 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	9960 KB	Output is correct
2	Correct	91 ms	9888 KB	Output is correct
3	Correct	89 ms	9752 KB	Output is correct
4	Correct	93 ms	9700 KB	Output is correct
5	Correct	91 ms	9496 KB	Output is correct
6	Correct	91 ms	9852 KB	Output is correct
7	Correct	92 ms	9796 KB	Output is correct
8	Correct	91 ms	9732 KB	Output is correct
9	Correct	91 ms	9708 KB	Output is correct
10	Correct	89 ms	9640 KB	Output is correct
11	Correct	91 ms	9612 KB	Output is correct
12	Correct	107 ms	10616 KB	Output is correct
13	Correct	104 ms	10692 KB	Output is correct
14	Correct	109 ms	10536 KB	Output is correct
15	Correct	105 ms	10496 KB	Output is correct
16	Correct	103 ms	10268 KB	Output is correct
17	Correct	105 ms	10616 KB	Output is correct
18	Correct	107 ms	10196 KB	Output is correct
19	Correct	108 ms	10496 KB	Output is correct
20	Correct	103 ms	10488 KB	Output is correct
21	Correct	104 ms	10636 KB	Output is correct
22	Correct	110 ms	10636 KB	Output is correct
23	Correct	106 ms	10364 KB	Output is correct
24	Correct	108 ms	10568 KB	Output is correct
25	Correct	112 ms	10716 KB	Output is correct
26	Correct	110 ms	10508 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	9960 KB	Output is correct
2	Correct	91 ms	9888 KB	Output is correct
3	Correct	89 ms	9752 KB	Output is correct
4	Correct	93 ms	9700 KB	Output is correct
5	Correct	91 ms	9496 KB	Output is correct
6	Correct	91 ms	9852 KB	Output is correct
7	Correct	92 ms	9796 KB	Output is correct
8	Correct	91 ms	9732 KB	Output is correct
9	Correct	91 ms	9708 KB	Output is correct
10	Correct	89 ms	9640 KB	Output is correct
11	Correct	91 ms	9612 KB	Output is correct
12	Correct	107 ms	10616 KB	Output is correct
13	Correct	104 ms	10692 KB	Output is correct
14	Correct	109 ms	10536 KB	Output is correct
15	Correct	105 ms	10496 KB	Output is correct
16	Correct	103 ms	10268 KB	Output is correct
17	Correct	105 ms	10616 KB	Output is correct
18	Correct	107 ms	10196 KB	Output is correct
19	Correct	108 ms	10496 KB	Output is correct
20	Correct	103 ms	10488 KB	Output is correct
21	Correct	104 ms	10636 KB	Output is correct
22	Correct	110 ms	10636 KB	Output is correct
23	Correct	106 ms	10364 KB	Output is correct
24	Correct	108 ms	10568 KB	Output is correct
25	Correct	112 ms	10716 KB	Output is correct
26	Correct	110 ms	10508 KB	Output is correct
27	Correct	187 ms	15152 KB	Output is correct
28	Correct	192 ms	15516 KB	Output is correct
29	Correct	206 ms	15584 KB	Output is correct
30	Correct	194 ms	15440 KB	Output is correct
31	Correct	192 ms	15472 KB	Output is correct
32	Correct	214 ms	15904 KB	Output is correct
33	Correct	188 ms	15256 KB	Output is correct
34	Correct	213 ms	15440 KB	Output is correct
35	Correct	195 ms	15292 KB	Output is correct
36	Correct	202 ms	15248 KB	Output is correct
37	Correct	183 ms	15172 KB	Output is correct
38	Correct	191 ms	15312 KB	Output is correct
39	Correct	197 ms	15776 KB	Output is correct
40	Correct	198 ms	15416 KB	Output is correct
41	Correct	193 ms	15500 KB	Output is correct
42	Correct	196 ms	15548 KB	Output is correct
43	Correct	192 ms	15464 KB	Output is correct
44	Correct	224 ms	15780 KB	Output is correct
45	Correct	201 ms	15388 KB	Output is correct
46	Correct	203 ms	15600 KB	Output is correct
47	Correct	206 ms	15832 KB	Output is correct
48	Correct	215 ms	15692 KB	Output is correct
49	Correct	186 ms	15420 KB	Output is correct
50	Correct	190 ms	15564 KB	Output is correct
51	Correct	202 ms	15500 KB	Output is correct

Subtask #4

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	9960 KB	Output is correct
2	Correct	91 ms	9888 KB	Output is correct
3	Correct	89 ms	9752 KB	Output is correct
4	Correct	93 ms	9700 KB	Output is correct
5	Correct	91 ms	9496 KB	Output is correct
6	Correct	91 ms	9852 KB	Output is correct
7	Correct	92 ms	9796 KB	Output is correct
8	Correct	91 ms	9732 KB	Output is correct
9	Correct	91 ms	9708 KB	Output is correct
10	Correct	89 ms	9640 KB	Output is correct
11	Correct	91 ms	9612 KB	Output is correct
12	Correct	107 ms	10616 KB	Output is correct
13	Correct	104 ms	10692 KB	Output is correct
14	Correct	109 ms	10536 KB	Output is correct
15	Correct	105 ms	10496 KB	Output is correct
16	Correct	103 ms	10268 KB	Output is correct
17	Correct	105 ms	10616 KB	Output is correct
18	Correct	107 ms	10196 KB	Output is correct
19	Correct	108 ms	10496 KB	Output is correct
20	Correct	103 ms	10488 KB	Output is correct
21	Correct	104 ms	10636 KB	Output is correct
22	Correct	110 ms	10636 KB	Output is correct
23	Correct	106 ms	10364 KB	Output is correct
24	Correct	108 ms	10568 KB	Output is correct
25	Correct	112 ms	10716 KB	Output is correct
26	Correct	110 ms	10508 KB	Output is correct
27	Correct	187 ms	15152 KB	Output is correct
28	Correct	192 ms	15516 KB	Output is correct
29	Correct	206 ms	15584 KB	Output is correct
30	Correct	194 ms	15440 KB	Output is correct
31	Correct	192 ms	15472 KB	Output is correct
32	Correct	214 ms	15904 KB	Output is correct
33	Correct	188 ms	15256 KB	Output is correct
34	Correct	213 ms	15440 KB	Output is correct
35	Correct	195 ms	15292 KB	Output is correct
36	Correct	202 ms	15248 KB	Output is correct
37	Correct	183 ms	15172 KB	Output is correct
38	Correct	191 ms	15312 KB	Output is correct
39	Correct	197 ms	15776 KB	Output is correct
40	Correct	198 ms	15416 KB	Output is correct
41	Correct	193 ms	15500 KB	Output is correct
42	Correct	196 ms	15548 KB	Output is correct
43	Correct	192 ms	15464 KB	Output is correct
44	Correct	224 ms	15780 KB	Output is correct
45	Correct	201 ms	15388 KB	Output is correct
46	Correct	203 ms	15600 KB	Output is correct
47	Correct	206 ms	15832 KB	Output is correct
48	Correct	215 ms	15692 KB	Output is correct
49	Correct	186 ms	15420 KB	Output is correct
50	Correct	190 ms	15564 KB	Output is correct
51	Correct	202 ms	15500 KB	Output is correct
52	Execution timed out	1146 ms	115732 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-