| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 384238 | Osama_Alkhodairy | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//~ #include "tickets.h"
#include "grader.cpp"
using namespace std;
#define ll long long
ll find_maximum(int k, vector <vector <int> > x) {
int n = x.size();
int m = x[0].size();
ll res = 0;
for(int i = 0 ; i < n ; i++){
for(int j = m - k ; j < m ; j++){
res += x[i][j];
}
}
vector <vector <int> > g(n, vector <int>(k));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
g[i][j] = x[i][j] + x[i][m - k + j];
}
}
set <pair <int, int> > s;
for(int i = 0 ; i < n ; i++){
s.insert(make_pair(g[i][0], i));
}
vector <int> cnt(n);
for(int i = 0 ; i < n * k / 2 ; i++){
int row = s.begin()->second;
s.erase(s.begin());
res -= g[row][cnt[row]];
cnt[row]++;
if(cnt[row] < k){
s.insert(make_pair(g[row][cnt[row]], row));
}
}
vector <pair <int, int> > all(n);
for(int i = 0 ; i < n ; i++){
all[i] = make_pair(cnt[i], i);
}
vector <vector <int> > answer(n, vector <int>(m, -1));
vector <int> l(n), r(n, m - 1);
for(int i = 0 ; i < k ; i++){
sort(all.rbegin(), all.rend());
for(int j = 0 ; j < n ; j++){
int row = all[j].second;
if(j < n / 2){
answer[row][l[row]++] = i;
all[j].first--;
}
else{
answer[row][r[row]--] = i;
}
}
}
allocate_tickets(answer);
return res;
}