Submission #433429

#TimeUsernameProblemLanguageResultExecution timeMemory
433429KerimCarnival Tickets (IOI20_tickets)C++17
100 / 100
893 ms66484 KiB
#include <bits/stdc++.h> #include "tickets.h" #define MAXN 100009 #define INF 1000000007 #define mp(x,y) make_pair(x,y) #define all(v) v.begin(),v.end() #define pb(x) push_back(x) #define wr cout<<"----------------"<<endl; #define ppb() pop_back() #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++) #define ff first #define ss second #define my_little_dodge 46 #define debug(x) cerr<< #x <<" = "<< x<<endl; using namespace std; typedef long long ll; typedef pair<int,int> PII; template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} using namespace std; const int N=1502; int l[N],r[N],ind[N],a[N][N]; bool cmp(int x,int y){ return (l[x]>l[y]); } long long find_maximum(int k, vector<vector<int>> arr) { int n = arr.size(); int m = arr[0].size(); for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i+1][j+1]=arr[i][j]; vector<vector<int>> ans; for (int i = 0; i < n; i++) { vector<int> row(m,-1); ans.push_back(row); } priority_queue<PII,vector<PII>,greater<PII> >q; ll S=0; for(int i=1;i<=n;i++){ r[i]=m-k+1; l[i]=1; q.push(mp(a[i][r[i]]+a[i][l[i]],i)); for(int j=m-k+1;j<=m;j++) S+=a[i][j]; } for(int rd=1;rd<=(n*k)/2;rd++){ PII nd=q.top();q.pop(); S-=nd.ff; int i=nd.ss; l[i]++;r[i]++; if(r[i]<=m) q.push(mp(a[i][r[i]]+a[i][l[i]],i)); } for(int i=1;i<=n;i++)ind[i]=i; for(int i=1;i<=n;i++)l[i]--,r[i]--; while(k--){ sort(ind+1,ind+n+1,cmp); for(int i=1;i<=n/2;i++) ans[ind[i]-1][--l[ind[i]]]=k; for(int i=n/2+1;i<=n;i++) ans[ind[i]-1][r[ind[i]]++]=k; } allocate_tickets(ans); return S; }
#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...