Submission #164304

#TimeUsernameProblemLanguageResultExecution timeMemory
164304fluffypotatoArt Exhibition (JOI18_art)Java
50 / 100
1146 ms115732 KiB
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;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...