oj.uz

Submission #381311

# Submission time Handle Problem Language Result Execution time Memory
381311 2021-03-25T03:06:31 Z timg8710 Sails (IOI07_sails) Java 11
25 / 100
 1000 ms 22576 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 = 100_000; 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 145 ms 13052 KB Output is correct
2 Correct 150 ms 13144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 13144 KB Output is correct
2 Correct 152 ms 13128 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 13144 KB Output is correct
2 Correct 153 ms 13144 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 16276 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 1096 ms 18680 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 19712 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 20880 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 1087 ms 21860 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 1086 ms 22576 KB Time limit exceeded
2 Halted 0 ms 0 KB -