답안 #164308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164308	2019-11-19T06:33:43 Z	fluffypotato	Art Exhibition (JOI18_art)	Java 11	50 / 100	1000 ms	129244 KB

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;
//        Integer[]bob=new Integer[400];
//        Arrays.sort(bob);
        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);
        }
        sort(arr,0,n-1);
        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();
    }
    static void merge(pair arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        pair L[] = new pair [n1];
        pair R[] = new pair [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] =  (arr[l + i]);
        for (int j=0; j<n2; ++j)
            R[j] = (arr[m + 1+ j]);


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i].size <= R[j].size)
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    static void sort(pair arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
}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

#	결과	실행 시간	메모리	Grader output
1	Correct	103 ms	9716 KB	Output is correct
2	Correct	91 ms	9724 KB	Output is correct
3	Correct	91 ms	9844 KB	Output is correct
4	Correct	94 ms	9836 KB	Output is correct
5	Correct	91 ms	9592 KB	Output is correct
6	Correct	91 ms	9548 KB	Output is correct
7	Correct	88 ms	9652 KB	Output is correct
8	Correct	91 ms	9640 KB	Output is correct
9	Correct	96 ms	9712 KB	Output is correct
10	Correct	100 ms	9860 KB	Output is correct
11	Correct	90 ms	9852 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	103 ms	9716 KB	Output is correct
2	Correct	91 ms	9724 KB	Output is correct
3	Correct	91 ms	9844 KB	Output is correct
4	Correct	94 ms	9836 KB	Output is correct
5	Correct	91 ms	9592 KB	Output is correct
6	Correct	91 ms	9548 KB	Output is correct
7	Correct	88 ms	9652 KB	Output is correct
8	Correct	91 ms	9640 KB	Output is correct
9	Correct	96 ms	9712 KB	Output is correct
10	Correct	100 ms	9860 KB	Output is correct
11	Correct	90 ms	9852 KB	Output is correct
12	Correct	108 ms	10348 KB	Output is correct
13	Correct	105 ms	10496 KB	Output is correct
14	Correct	109 ms	10424 KB	Output is correct
15	Correct	105 ms	10624 KB	Output is correct
16	Correct	148 ms	10512 KB	Output is correct
17	Correct	103 ms	10820 KB	Output is correct
18	Correct	107 ms	10644 KB	Output is correct
19	Correct	107 ms	10508 KB	Output is correct
20	Correct	105 ms	10488 KB	Output is correct
21	Correct	107 ms	10332 KB	Output is correct
22	Correct	102 ms	10372 KB	Output is correct
23	Correct	113 ms	10596 KB	Output is correct
24	Correct	101 ms	10724 KB	Output is correct
25	Correct	115 ms	10288 KB	Output is correct
26	Correct	101 ms	10452 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	103 ms	9716 KB	Output is correct
2	Correct	91 ms	9724 KB	Output is correct
3	Correct	91 ms	9844 KB	Output is correct
4	Correct	94 ms	9836 KB	Output is correct
5	Correct	91 ms	9592 KB	Output is correct
6	Correct	91 ms	9548 KB	Output is correct
7	Correct	88 ms	9652 KB	Output is correct
8	Correct	91 ms	9640 KB	Output is correct
9	Correct	96 ms	9712 KB	Output is correct
10	Correct	100 ms	9860 KB	Output is correct
11	Correct	90 ms	9852 KB	Output is correct
12	Correct	108 ms	10348 KB	Output is correct
13	Correct	105 ms	10496 KB	Output is correct
14	Correct	109 ms	10424 KB	Output is correct
15	Correct	105 ms	10624 KB	Output is correct
16	Correct	148 ms	10512 KB	Output is correct
17	Correct	103 ms	10820 KB	Output is correct
18	Correct	107 ms	10644 KB	Output is correct
19	Correct	107 ms	10508 KB	Output is correct
20	Correct	105 ms	10488 KB	Output is correct
21	Correct	107 ms	10332 KB	Output is correct
22	Correct	102 ms	10372 KB	Output is correct
23	Correct	113 ms	10596 KB	Output is correct
24	Correct	101 ms	10724 KB	Output is correct
25	Correct	115 ms	10288 KB	Output is correct
26	Correct	101 ms	10452 KB	Output is correct
27	Correct	252 ms	16052 KB	Output is correct
28	Correct	229 ms	15860 KB	Output is correct
29	Correct	187 ms	15936 KB	Output is correct
30	Correct	199 ms	15660 KB	Output is correct
31	Correct	188 ms	15724 KB	Output is correct
32	Correct	182 ms	16060 KB	Output is correct
33	Correct	176 ms	15688 KB	Output is correct
34	Correct	177 ms	15956 KB	Output is correct
35	Correct	226 ms	15800 KB	Output is correct
36	Correct	171 ms	15644 KB	Output is correct
37	Correct	201 ms	15744 KB	Output is correct
38	Correct	185 ms	15720 KB	Output is correct
39	Correct	195 ms	15940 KB	Output is correct
40	Correct	231 ms	16580 KB	Output is correct
41	Correct	186 ms	15860 KB	Output is correct
42	Correct	179 ms	15832 KB	Output is correct
43	Correct	177 ms	15588 KB	Output is correct
44	Correct	199 ms	15816 KB	Output is correct
45	Correct	175 ms	15472 KB	Output is correct
46	Correct	180 ms	15776 KB	Output is correct
47	Correct	186 ms	15732 KB	Output is correct
48	Correct	169 ms	15076 KB	Output is correct
49	Correct	182 ms	15944 KB	Output is correct
50	Correct	180 ms	15772 KB	Output is correct
51	Correct	198 ms	15628 KB	Output is correct

Subtask #4
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	103 ms	9716 KB	Output is correct
2	Correct	91 ms	9724 KB	Output is correct
3	Correct	91 ms	9844 KB	Output is correct
4	Correct	94 ms	9836 KB	Output is correct
5	Correct	91 ms	9592 KB	Output is correct
6	Correct	91 ms	9548 KB	Output is correct
7	Correct	88 ms	9652 KB	Output is correct
8	Correct	91 ms	9640 KB	Output is correct
9	Correct	96 ms	9712 KB	Output is correct
10	Correct	100 ms	9860 KB	Output is correct
11	Correct	90 ms	9852 KB	Output is correct
12	Correct	108 ms	10348 KB	Output is correct
13	Correct	105 ms	10496 KB	Output is correct
14	Correct	109 ms	10424 KB	Output is correct
15	Correct	105 ms	10624 KB	Output is correct
16	Correct	148 ms	10512 KB	Output is correct
17	Correct	103 ms	10820 KB	Output is correct
18	Correct	107 ms	10644 KB	Output is correct
19	Correct	107 ms	10508 KB	Output is correct
20	Correct	105 ms	10488 KB	Output is correct
21	Correct	107 ms	10332 KB	Output is correct
22	Correct	102 ms	10372 KB	Output is correct
23	Correct	113 ms	10596 KB	Output is correct
24	Correct	101 ms	10724 KB	Output is correct
25	Correct	115 ms	10288 KB	Output is correct
26	Correct	101 ms	10452 KB	Output is correct
27	Correct	252 ms	16052 KB	Output is correct
28	Correct	229 ms	15860 KB	Output is correct
29	Correct	187 ms	15936 KB	Output is correct
30	Correct	199 ms	15660 KB	Output is correct
31	Correct	188 ms	15724 KB	Output is correct
32	Correct	182 ms	16060 KB	Output is correct
33	Correct	176 ms	15688 KB	Output is correct
34	Correct	177 ms	15956 KB	Output is correct
35	Correct	226 ms	15800 KB	Output is correct
36	Correct	171 ms	15644 KB	Output is correct
37	Correct	201 ms	15744 KB	Output is correct
38	Correct	185 ms	15720 KB	Output is correct
39	Correct	195 ms	15940 KB	Output is correct
40	Correct	231 ms	16580 KB	Output is correct
41	Correct	186 ms	15860 KB	Output is correct
42	Correct	179 ms	15832 KB	Output is correct
43	Correct	177 ms	15588 KB	Output is correct
44	Correct	199 ms	15816 KB	Output is correct
45	Correct	175 ms	15472 KB	Output is correct
46	Correct	180 ms	15776 KB	Output is correct
47	Correct	186 ms	15732 KB	Output is correct
48	Correct	169 ms	15076 KB	Output is correct
49	Correct	182 ms	15944 KB	Output is correct
50	Correct	180 ms	15772 KB	Output is correct
51	Correct	198 ms	15628 KB	Output is correct
52	Execution timed out	1137 ms	129244 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

답안 #164308

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 50.0