Submission #305836

#TimeUsernameProblemLanguageResultExecution timeMemory
305836DormiCarnival Tickets (IOI20_tickets)C++14
62 / 100
3110 ms215156 KiB
#include "bits/stdc++.h" #include "tickets.h" using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<typename T> int sz(const T &a){return int(a.size());} set<int> used[1501][2]; ll find_maximum(int k, vector<vector<int>> x){ int n=sz(x),m=sz(x[0]); ll ans=0; priority_queue<pair<ll,pair<int,pii>>> q; vector<int> order; for(int i=0;i<n;i++){ order.push_back(i); for(int j=1;j<=k;j++){ ans+=x[i][m-j]; used[i][0].insert(m-j); q.push({-x[i][j-1]-x[i][m-k+j-1],{i,{j-1,m-k+j-1}}}); } } for(int i=0;i<n*k/2;i++){ auto cur=q.top(); q.pop(); used[cur.second.first][0].erase(used[cur.second.first][0].find(cur.second.second.second)); used[cur.second.first][1].insert(cur.second.second.first); ans+=cur.first; } vector<vector<int>> ret(n,vector<int>(m,-1)); for(int i=0;i<k;i++){ sort(order.begin(),order.end(),[&](auto &lhs, auto &rhs){ return sz(used[rhs][0])<sz(used[lhs][0]); }); for(int j=0;j<n;j++){ int loc=(j>=n/2); assert(sz(used[order[j]][loc])); ret[order[j]][*used[order[j]][loc].begin()]=i; used[order[j]][loc].erase(used[order[j]][loc].begin()); } } allocate_tickets(ret); return ans; }
#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...