Submission #1210019

#TimeUsernameProblemLanguageResultExecution timeMemory
1210019simona1230Carnival Tickets (IOI20_tickets)C++20
100 / 100
865 ms103460 KiB
#include "tickets.h" #include <vector> #include <bits/stdc++.h> using namespace std; int a[1501][1501]; bool cmp(pair<int,int> p1,pair<int,int> p2) { return a[p1.first][p1.second]<a[p2.first][p2.second]; } int nn,mm; long long dp[128][6501]; long long pr[128][128]; int tk[128][6501]; int take[1501]; long long find_maximum(int k, std::vector<std::vector<int>> x) { nn=x.size(); mm=x[0].size(); vector<long long> all; vector<vector<int> > t=x; vector<pair<int,int> > v; for(int i=0; i<x.size(); i++) { for(int j=0; j<x[i].size(); j++) { a[i][j]=x[i][j]; if(j==0)pr[i][j]=a[i][j]; else pr[i][j]=pr[i][j-1]+a[i][j]; } } priority_queue<pair<long long,long long> > q; for(int i=0;i<nn;i++) { take[i]=k; q.push({a[i][mm-1]+a[i][k-1],i}); } for(int i=0;i<nn*k/2;i++) { pair<long long,long long> tp=q.top(); q.pop(); take[tp.second]--; if(take[tp.second]!=0) q.push({a[tp.second][mm-1-k+take[tp.second]]+a[tp.second][take[tp.second]-1],tp.second}); } for(int i=nn-1;i>=0;i--) { //cout<<i<<" "<<tk[i][lf]<<" "<<lf<<endl; int ctk=take[i]; for(int j=0;j<ctk;j++) all.push_back(a[i][j]),v.push_back({i,j}); for(int j=mm-1;j>mm-1-k+ctk;j--) all.push_back(a[i][j]),v.push_back({i,j}); } sort(all.begin(),all.end()); sort(v.begin(),v.end(),cmp); vector<int> s[1501],b[1501]; long long sum=0; for(int i=0; i<all.size(); i++) { //cout<<all[i]<<" "; if(i<all.size()/2)s[v[i].first].push_back(v[i].second),sum-=all[i]; else b[v[i].first].push_back(v[i].second),sum+=all[i]; } //cout<<endl; pair<int,int> p[1501]; for(int i=0; i<k; i++) p[i].first=0,p[i].second=i; for(int i=0; i<x.size(); i++) { sort(p,p+k); for(int j=0;j<mm;j++) t[i][j]=-1; for(int j=0; j<s[i].size(); j++) { t[i][s[i][j]]=p[j].second; p[j].first++; //cout<<s[i][j]<<"- "; } //cout<<endl; for(int j=0; j<b[i].size(); j++) { t[i][b[i][j]]=p[j+s[i].size()].second; //cout<<b[i][j]<<"+ "; } //cout<<endl; } allocate_tickets(t); return sum; }
#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...