| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 301670 | ijxjdjd | 카니발 티켓 (IOI20_tickets) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class tickets {
long find_maximum(int K, int[][] x) {
int N = x.length;
int M = x[0].length;
int[][] S = new int[N*K][2];
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
S[i*K + j][0] = i;
S[i*K + j][1] = j;
}
}
Arrays.sort(S, new Comparator<int[]>() {
@Override
public int compare(int[] ints, int[] t1) {
return -Integer.compare(-x[ints[0]][ints[1]] - x[ints[0]][M - K + ints[1]], -x[t1[0]][t1[1]] - x[t1[0]][M-K+ints[1]]);
}
});
long res = 0;
ArrayList<Integer>[] low = new ArrayList[N];
ArrayList<Integer>[] high = new ArrayList[N];
for (int i = 0; i < N; i++) {
low[i] = new ArrayList<>();
high[i] = new ArrayList<>();
}
for (int i = 0; i < S.length/2; i++) {
low[S[i][0]].add(S[i][1]);
}
int[][] ans = new int[N][M];
ArrayList<int[]>[] rounds = new ArrayList[K];
for (int j = 0; j < K; j++) {
rounds[j] = new ArrayList<>();
}
for (int i = 0; i < N; i++) {
res += i;
}
int k = 0;
for (int id = 0; id < N; id++) {
int bef = k;
for (int a : low[id]) {
rounds[k].add(new int[]{id, a});
res -= x[id][a];
k++;
if (k == K) {
k = 0;
}
}
int c = 1;
for (int i = k; i != bef;) {
res += x[id][M-c];
rounds[i].add(new int[]{id, M-c});
c++;
i++;
if (i == K) {
i = 0;
}
}
}
for (int j = 0; j < N; j++) {
Arrays.fill(ans[j], -1);
}
for (int j = 0; j < K; j++) {
for (int[] s : rounds[j]) {
ans[s[0]][s[1]] = j;
}
}
allocate_tickets(ans);
return res;
}
}