Submission #601156

#TimeUsernameProblemLanguageResultExecution timeMemory
601156yutabiCarnival Tickets (IOI20_tickets)C++14
25 / 100
959 ms118472 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; #define pb push_back typedef pair <int,int> ii; long long find_maximum(int k, std::vector<std::vector<int>> X) { int n = X.size(); int m = X[0].size(); vector <pair <int,ii> > x; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { x.pb(make_pair(X[i][j],ii(i,j))); } } sort(x.begin(),x.end()); vector <vector <ii> > small_values(n); vector <vector <ii> > big_values(n); for(int i=0;i<n*m/2;i++) { small_values[x[i].second.first].pb(ii(x[i].first,x[i].second.second)); } for(int i=n*m/2;i<n*m;i++) { big_values[x[i].second.first].pb(ii(x[i].first,x[i].second.second)); } /*for(int i=0;i<n;i++) { for(int j=0;j<small_values[i].size();j++) { printf("%d %d ",small_values[i][j].first,small_values[i][j].second); } printf(" "); for(int j=0;j<big_values[i].size();j++) { printf("%d %d ",big_values[i][j].first,big_values[i][j].second); } printf("\n"); }*/ vector <vector <int> > answer(n,vector <int> (k,-1)); long long ans=0; for(int i=0;i<k;i++) { int small=n/2; int big=n/2; vector <bool> t(n,0); for(int j=0;j<n;j++) { if(small_values[j].size()==0) { t[j]=1; big--; ans+=big_values[j].back().first; answer[j][big_values[j].back().second]=i; big_values[j].pop_back(); } else if(big_values[j].size()==0) { t[j]=1; small--; ans-=small_values[j].back().first; answer[j][small_values[j].back().second]=i; small_values[j].pop_back(); } } for(int j=0;j<n;j++) { if(t[j]==0) { if(big>0) { t[j]=1; big--; ans+=big_values[j].back().first; answer[j][big_values[j].back().second]=i; big_values[j].pop_back(); } else { t[j]=1; small--; ans-=small_values[j].back().first; answer[j][small_values[j].back().second]=i; small_values[j].pop_back(); } } } } allocate_tickets(answer); 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...