Submission #631275

#	Time	Username	Problem	Language	Result	Execution time	Memory
631275		kyaruru	Schools (IZhO13_school)	Java	30 / 100	2070 ms	32664 KiB

school

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

public class school {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<int[]> m=new PriorityQueue<>((o1, o2) -> (o1[0]-o1[1])-(o2[0]-o2[1]));
        PriorityQueue<int[]> s=new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);
        PriorityQueue<int[]> save=new PriorityQueue<>((o1, o2) -> o2[0]-o1[0]);
        String[] sa=bf.readLine().split(" ");
        int a=Integer.parseInt(sa[0]),p=Integer.parseInt(sa[1]),q=Integer.parseInt(sa[2]);
        int[][] k=new int[a][2];
        for(int i=0; i<a; i++){
            sa=bf.readLine().split(" ");
            int x=Integer.parseInt(sa[0]),y=Integer.parseInt(sa[1]);
            k[i][0]=x; k[i][1]=y;
        }
        Arrays.sort(k,(o1, o2) -> o2[0]-o1[0]);
        for(int i=0; i<a; i++){
            if(p==0){
                if(s.size()<q) s.add(k[i]);
                else{
                    if(!s.isEmpty() && s.peek()[1]<k[i][1]){
                        s.poll();
                        s.add(k[i]);
                    }
                }
            }
            else {
                if (m.size() < p) m.add(k[i]);
                else{
                    if(s.size()<q){
                        int[] r=m.poll();
                        if(r[0]-r[1]>=k[i][0]-k[i][1]) {
                            s.add(k[i]);
                            m.add(r);
                        }
                        else {
                            s.add(r);
                            m.add(k[i]);
                        }
                    }
                    else{
                        if(!s.isEmpty() && s.peek()[1]<k[i][1]){
                            save.add(s.poll());
                            s.add(k[i]);
                        }
                    }
                }
            }
        }
        long sum=0;
        while(!m.isEmpty()) save.add(m.poll());
        while(p-->0) sum+=save.poll()[0];
        while(!s.isEmpty()) sum+=s.poll()[1];
        System.out.println(sum);
    }
}

• Subtask 1: 30 / 100