oj.uz

Submission #381309

# Submission time Handle Problem Language Result Execution time Memory
381309 2021-03-25T03:02:04 Z timg8710 Sails (IOI07_sails) Java 11
25 / 100
 1000 ms 23164 KB 
// 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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 9196 KB Output is correct
2 Correct 83 ms 9180 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 9196 KB Output is correct
2 Correct 84 ms 9196 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9276 KB Output is correct
2 Correct 85 ms 9120 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 191 ms 13916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 419 ms 16292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 16980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 18860 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 22180 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 21504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 22696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 23164 KB Time limit exceeded
2 Halted 0 ms 0 KB -