| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1062930 | Kipras | 카니발 티켓 (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#include "tickets.h"
constexpr ll maxN = 1510;
vector<pair<ll, ll>> colours[maxN];
vector<vector<int>> ans;
long long find_maximum(int k, vector<vector<int>> a) {
ll coloursN = a.size();
ll n = a[0].size();
ll res=0;
for(int i = 0; i < coloursN; i++) {
vector<ll> tmp;
for(int x = 0; x < n; x++) {
colours[i].push_back({a[i][x], x});
tmp.push_back({-1});
}
ans.push_back(tmp);
}
for(int i = 0; i < coloursN; i++)
sort(colours[i].begin(), colours[i].end());
priority_queue<pair<ll, pair<ll, pair<ll, ll>>>> q;
for(int i = 0; i < coloursN; i++) {
for(int x = 0; x < k; x++) {
res+=colours[i][x].first;
ans[i][colours[i][x].second]=x;
q.push({-colours[i][x].first-colours[i][n-k+x].first, {i, {x, n-k+x}}});
}
}
for(int i = 0; i < k*(coloursN/2); i++) {
pair<ll, pair<ll, pair<ll, ll>>> tmpPair = q.top();
q.pop();
res-= tmpPair.first;
ll color = tmpPair.second.first;
ll u = tmpPair.second.second.first;
ll v = tmpPair.second.second.second;
ans[color][v]=ans[color][u];
if(u!=v)ans[color][u]=-1;
}
allocate_tickets(ans);
return res;
}