oj.uz

Submission #319133

# Submission time Handle Problem Language Result Execution time Memory
319133 2020-11-04T03:13:16 Z KWang31 Carnival Tickets (IOI20_tickets) Java 11
100 / 100
 1842 ms 148972 KB 
import java.io.*; import java.util.*;
public class tickets {
    public 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);
        }
        Arrays.fill(lp,k-1);
        boolean[] b=new boolean[n];
        for(int i=0;i<n;i++) {
            
            for (int j = 0; j < k; j++) {
                ans-=x[i][j];
            }
            pq.add(new Pair(-x[i][k-1]-x[i][m-1],i));
        }
        
        for (int i = 0; i < k*n/2; i++) {
            Pair p=pq.poll();
            ans-=p.val; lp[p.ind]--;
            if(lp[p.ind]>=0){
                pq.add(new Pair(-x[p.ind][lp[p.ind]]-x[p.ind][m-k+lp[p.ind]],p.ind));
                //System.out.println(p.ind+" "+lp[p.ind]+" "+(-x[p.ind][lp[p.ind]]-x[p.ind][m-k+lp[p.ind]]));
            }
            
            
        }
        pq=new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.add(new Pair(lp[i]+1,i));//Smallest lp values will start with +
        }
        
        int[] pt=new int[n];//Pointer
        for (int i = 1; i <= k; i++) {
            Arrays.fill(b,false);
            for (int j = 0; j < n/2; j++) {
                Pair p=pq.poll();
                b[p.ind]=true; s[p.ind][m-i+pt[p.ind]]=i-1;
            }
            pq=new PriorityQueue<>();
            for (int j = 0; j < n; j++) {
                if(!b[j]){
                    s[j][pt[j]]=i-1; pt[j]++; lp[j]--;
                    
                    
                }
                pq.add(new Pair(lp[j],j));
                
                
                
            }
        }
        
       //System.out.println(Arrays.toString(lp));
        
        grader.allocate_tickets(s);
        return ans;
    }

    
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 11360 KB Output is correct
2 Correct 88 ms 11328 KB Output is correct
3 Correct 86 ms 11400 KB Output is correct
4 Correct 86 ms 11572 KB Output is correct
5 Correct 95 ms 11616 KB Output is correct
6 Correct 119 ms 12356 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 11448 KB Output is correct
2 Correct 82 ms 11392 KB Output is correct
3 Correct 87 ms 11444 KB Output is correct
4 Correct 121 ms 12944 KB Output is correct
5 Correct 237 ms 20956 KB Output is correct
6 Correct 716 ms 88460 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 11168 KB Output is correct
2 Correct 87 ms 11440 KB Output is correct
3 Correct 90 ms 11484 KB Output is correct
4 Correct 127 ms 12456 KB Output is correct
5 Correct 339 ms 25316 KB Output is correct
6 Correct 1360 ms 115216 KB Output is correct
7 Correct 1344 ms 123396 KB Output is correct
8 Correct 201 ms 16136 KB Output is correct
9 Correct 85 ms 11456 KB Output is correct
10 Correct 85 ms 11360 KB Output is correct
11 Correct 83 ms 11436 KB Output is correct
12 Correct 233 ms 17396 KB Output is correct
13 Correct 345 ms 24132 KB Output is correct
14 Correct 344 ms 24908 KB Output is correct
15 Correct 1471 ms 127080 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 11556 KB Output is correct
2 Correct 85 ms 11268 KB Output is correct
3 Correct 82 ms 11444 KB Output is correct
4 Correct 145 ms 13796 KB Output is correct
5 Correct 466 ms 31048 KB Output is correct
6 Correct 213 ms 15968 KB Output is correct
7 Correct 247 ms 15776 KB Output is correct
8 Correct 1634 ms 147076 KB Output is correct
9 Correct 1664 ms 144152 KB Output is correct
10 Correct 1808 ms 146040 KB Output is correct
11 Correct 1841 ms 148840 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11440 KB Output is correct
2 Correct 116 ms 12716 KB Output is correct
3 Correct 121 ms 12508 KB Output is correct
4 Correct 125 ms 12592 KB Output is correct
5 Correct 134 ms 12432 KB Output is correct
6 Correct 146 ms 12764 KB Output is correct
7 Correct 103 ms 11460 KB Output is correct
8 Correct 100 ms 11572 KB Output is correct
9 Correct 133 ms 12564 KB Output is correct
10 Correct 128 ms 12560 KB Output is correct
11 Correct 151 ms 13780 KB Output is correct
12 Correct 156 ms 13656 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 11440 KB Output is correct
2 Correct 116 ms 12716 KB Output is correct
3 Correct 121 ms 12508 KB Output is correct
4 Correct 125 ms 12592 KB Output is correct
5 Correct 134 ms 12432 KB Output is correct
6 Correct 146 ms 12764 KB Output is correct
7 Correct 103 ms 11460 KB Output is correct
8 Correct 100 ms 11572 KB Output is correct
9 Correct 133 ms 12564 KB Output is correct
10 Correct 128 ms 12560 KB Output is correct
11 Correct 151 ms 13780 KB Output is correct
12 Correct 156 ms 13656 KB Output is correct
13 Correct 257 ms 21436 KB Output is correct
14 Correct 248 ms 21108 KB Output is correct
15 Correct 412 ms 27004 KB Output is correct
16 Correct 439 ms 27092 KB Output is correct
17 Correct 122 ms 12192 KB Output is correct
18 Correct 126 ms 12760 KB Output is correct
19 Correct 121 ms 11800 KB Output is correct
20 Correct 381 ms 26024 KB Output is correct
21 Correct 415 ms 26716 KB Output is correct
22 Correct 406 ms 26872 KB Output is correct
23 Correct 465 ms 29352 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 11360 KB Output is correct
2 Correct 88 ms 11328 KB Output is correct
3 Correct 86 ms 11400 KB Output is correct
4 Correct 86 ms 11572 KB Output is correct
5 Correct 95 ms 11616 KB Output is correct
6 Correct 119 ms 12356 KB Output is correct
7 Correct 86 ms 11448 KB Output is correct
8 Correct 82 ms 11392 KB Output is correct
9 Correct 87 ms 11444 KB Output is correct
10 Correct 121 ms 12944 KB Output is correct
11 Correct 237 ms 20956 KB Output is correct
12 Correct 716 ms 88460 KB Output is correct
13 Correct 89 ms 11168 KB Output is correct
14 Correct 87 ms 11440 KB Output is correct
15 Correct 90 ms 11484 KB Output is correct
16 Correct 127 ms 12456 KB Output is correct
17 Correct 339 ms 25316 KB Output is correct
18 Correct 1360 ms 115216 KB Output is correct
19 Correct 1344 ms 123396 KB Output is correct
20 Correct 201 ms 16136 KB Output is correct
21 Correct 85 ms 11456 KB Output is correct
22 Correct 85 ms 11360 KB Output is correct
23 Correct 83 ms 11436 KB Output is correct
24 Correct 233 ms 17396 KB Output is correct
25 Correct 345 ms 24132 KB Output is correct
26 Correct 344 ms 24908 KB Output is correct
27 Correct 1471 ms 127080 KB Output is correct
28 Correct 87 ms 11556 KB Output is correct
29 Correct 85 ms 11268 KB Output is correct
30 Correct 82 ms 11444 KB Output is correct
31 Correct 145 ms 13796 KB Output is correct
32 Correct 466 ms 31048 KB Output is correct
33 Correct 213 ms 15968 KB Output is correct
34 Correct 247 ms 15776 KB Output is correct
35 Correct 1634 ms 147076 KB Output is correct
36 Correct 1664 ms 144152 KB Output is correct
37 Correct 1808 ms 146040 KB Output is correct
38 Correct 1841 ms 148840 KB Output is correct
39 Correct 83 ms 11440 KB Output is correct
40 Correct 116 ms 12716 KB Output is correct
41 Correct 121 ms 12508 KB Output is correct
42 Correct 125 ms 12592 KB Output is correct
43 Correct 134 ms 12432 KB Output is correct
44 Correct 146 ms 12764 KB Output is correct
45 Correct 103 ms 11460 KB Output is correct
46 Correct 100 ms 11572 KB Output is correct
47 Correct 133 ms 12564 KB Output is correct
48 Correct 128 ms 12560 KB Output is correct
49 Correct 151 ms 13780 KB Output is correct
50 Correct 156 ms 13656 KB Output is correct
51 Correct 257 ms 21436 KB Output is correct
52 Correct 248 ms 21108 KB Output is correct
53 Correct 412 ms 27004 KB Output is correct
54 Correct 439 ms 27092 KB Output is correct
55 Correct 122 ms 12192 KB Output is correct
56 Correct 126 ms 12760 KB Output is correct
57 Correct 121 ms 11800 KB Output is correct
58 Correct 381 ms 26024 KB Output is correct
59 Correct 415 ms 26716 KB Output is correct
60 Correct 406 ms 26872 KB Output is correct
61 Correct 465 ms 29352 KB Output is correct
62 Correct 322 ms 32872 KB Output is correct
63 Correct 386 ms 33668 KB Output is correct
64 Correct 731 ms 49196 KB Output is correct
65 Correct 1008 ms 97264 KB Output is correct
66 Correct 1254 ms 119932 KB Output is correct
67 Correct 234 ms 16276 KB Output is correct
68 Correct 197 ms 15004 KB Output is correct
69 Correct 731 ms 105508 KB Output is correct
70 Correct 1391 ms 129504 KB Output is correct
71 Correct 1842 ms 148972 KB Output is correct
72 Correct 1612 ms 132848 KB Output is correct
73 Correct 1566 ms 145416 KB Output is correct
74 Correct 1521 ms 121388 KB Output is correct
75 Correct 1334 ms 128856 KB Output is correct