Submission #381309

#	Time	Username	Problem	Language	Result	Execution time	Memory
381309		timg8710	Sails (IOI07_sails)	Java	25 / 100	1100 ms	23164 KiB

sails

// package olypmiads;

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

public class sails {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int N = Integer.parseInt(br.readLine());
        int[][] nums = new int[N][2];
        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()); nums[i] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
        }
        Arrays.sort(nums, (int[] a, int[] b) -> b[0] - a[0]);
        int l = 1;
        int r = N;
        
        while(l < r){
            int mid = (l+r)/2;
            if(good(mid, nums) != -1){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        pw.println(good(r, nums));
        pw.close();
        br.close();
    }
    
    static long good(int max, int[][] nums){
        int r = 0;
        long ret = 0;
        Queue<Integer> run = new PriorityQueue<>(Comparator.reverseOrder());
        for(int i = 10; i>=1; i--){
            while(r < nums.length && nums[r][0] >= i){
                run.add(nums[r][1]);
                r++;
            }
            long take = Math.min(run.size(), max);
            ret += take*(take-1)/2;
            List<Integer> taken = new ArrayList(); //this is messy but whatever its fine
            while(take > 0){
                taken.add(run.poll()-1); take--;
            }
            for(int j : taken) if(j != 0) run.add(j);
        }
        
        return run.isEmpty() ? ret : -1;
    }
}

Compilation message (stderr)

Note: sails.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10