Submission #428212

#TimeUsernameProblemLanguageResultExecution timeMemory
428212zoooma13Carnival Tickets (IOI20_tickets)C++14
100 / 100
901 ms56876 KiB
#include "bits/stdc++.h" #include "tickets.h" using namespace std; int n ,m ,k; vector <vector <int>> x; vector <vector <int>> construct(vector <int> pref){ vector <int> fh[n] ,sh[n]; for(int i = 0; i < n; i++){ for(int j = 0; j < pref[i]; j++) fh[i].push_back(j); for(int j = m-1; j >= m - (k-pref[i]); j--) sh[i].push_back(j); } int round_number = 0; vector <int> pos(n); vector<vector<int>> answer(n ,vector<int>(m ,-1)); for(int i = 0; i < n; i++) for(auto&c : fh[i]){ pos[i] = round_number; answer[i][c] = pos[i]; round_number = (round_number+1 == k? 0 : round_number+1); } for(int i = 0; i < n; i++) for(auto&c : sh[i]){ pos[i] = (pos[i]+1 == k? 0 : pos[i]+1); answer[i][c] = pos[i]; } return answer; } long long find_maximum(int _k, vector<vector<int>> _x) { x = _x; n = x.size(); m = x[0].size(); k = _k; vector <int> pref(n ,k); priority_queue <pair <int64_t ,int>> pq; int64_t tot = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < pref[i]; j++) tot -= x[i][j]; pq.push({x[i][pref[i]-1] + x[i][m-1-(k - pref[i])] ,i}); } for(int step = 0; step < n*k/2; step++){ auto p = pq.top(); pq.pop(); tot += p.first; int i = p.second; pref[i]--; if(pref[i]) pq.push({x[i][pref[i]-1] + x[i][m-1-(k - pref[i])] ,i}); } allocate_tickets(construct(pref)); return tot; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...