Submission #318732

#	Time	Username	Problem	Language	Result	Execution time	Memory
318732		KWang31	Carnival Tickets (IOI20_tickets)	Java	27 / 100	698 ms	84040 KiB

tickets

import java.io.*; import java.util.*;
public class tickets {
    static class Pair implements Comparable<Pair>{
        int val; int ind;
        public Pair(int a, int b){
            this.val=a; this.ind=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.ind>other.ind)return -1;
            return 1;
        }
    }
    public static long find_maximum(int k, int[][] x){
        long ans=0;
        PriorityQueue<Pair> pq=new PriorityQueue<>();
        int n=x.length; int m=x[0].length;
        int[] lp=new int[n]; // rp = (N-1) - i + lp
        int[][] s=new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(s[i],-1);
        }
        boolean[] b=new boolean[n];
        for(int i=0;i<k;i++) {
            
            for (int j = 0; j < n; j++) {
                ans+=x[j][m-1-i+lp[j]];
                
                pq.add(new Pair(x[j][lp[j]]+x[j][m-1-i+lp[j]],j));
                
            }
            b=new boolean[n];
            for (int j = 0; j < n/2; j++) {
                Pair p=pq.poll();
                ans-=p.val; s[p.ind][lp[p.ind]]=i;
                lp[p.ind]++; b[p.ind]=true;
                
            }
            for (int j = 0; j < n; j++) {
                if(!b[j]){
                    s[j][m-1-i+lp[j]]=i;
                }
            }
        }
        grader.allocate_tickets(s);
        return ans;
    }
    
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10