이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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));
for (int i = 0; i < n; i++) {
System.out.println(Arrays.toString(s[i]));
}
return ans;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |