Submission #164302

#	Time	Username	Problem	Language	Result	Execution time	Memory
164302		fluffypotato	Art Exhibition (JOI18_art)	Java	50 / 100	1097 ms	115264 KiB

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 50