Submission #1210004

#TimeUsernameProblemLanguageResultExecution timeMemory
1210004simona1230Carnival Tickets (IOI20_tickets)C++20
0 / 100
3095 ms20248 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]; 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]; } } for(int i=0; i<nn; i++) { for(int j=0; j<=nn*k/2; j++) { dp[i][j]=-1e12; if(i==0) { int h=j; if(h<=k) { long long curr=pr[i][mm-1]; if(h!=0)curr-=pr[i][h-1]; if(mm-1-k+h>=0)curr-=pr[i][mm-1-k+h]; dp[i][j]=curr; tk[i][j]=h; } } else for(int h=0; h<=min(j,k); h++) { long long curr=pr[i][mm-1]; if(h!=0)curr-=pr[i][h-1]; if(mm-1-k+h>=0)curr-=pr[i][mm-1-k+h]; if(i==0)dp[i][j]=max(dp[i][j],curr); else dp[i][j]=max(dp[i][j],dp[i-1][j-h]+curr); if(i==0&&dp[i][j]==curr||i!=0&&dp[i][j]==dp[i-1][j-h]+curr) tk[i][j]=h; } //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; } } int lf=nn*k/2; for(int i=nn-1;i>=0;i--) { //cout<<i<<" "<<tk[i][lf]<<" "<<lf<<endl; int ctk=tk[i][lf]; lf-=ctk; 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...