Submission #1215800

#TimeUsernameProblemLanguageResultExecution timeMemory
1215800cpdreamerCarnival Tickets (IOI20_tickets)C++17
11 / 100
3097 ms141156 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; const long long INF = 1e17; typedef long long ll; const ll MOD = (ll)1e9+7; #define P pair #define S second #define F first #define pb push_back #define V vector #define all(v) v.begin(), v.end() long long find_maximum(int k, std::vector<std::vector<int>> x) { int n=(int)x.size(); int m=(int)x[0].size(); int h=n/2; ll a=0; V<V<bool>>taken(n,V<bool>(m)); V<V<int>>ans(n,V<int>(m,-1)); int left[n],right[n]; multiset<int>val; for (int i=0;i<n;i++) { for (int j=m-1;j>m-1-k;j--) { taken[i][j]=true; val.insert(x[i][j]); } if (k!=m) { left[i]=0; } else { left[i]=-1; } right[i]=m-k; } for (int i=0;i<h*k;i++) { a+=*prev(val.end()); val.erase(prev(val.end())); } for (int i=0;i<n;i++) { while (true) { if (left[i]<0) break; if (right[i]>=m) break; if (right[i]-left[i]<1) break; if (x[i][right[i]]>*prev(val.end())) break; auto it=val.find(x[i][right[i]]); val.erase(it); val.insert(x[i][left[i]]); right[i]++; left[i]++; } } for (auto u:val) { a-=u; } V<V<int>>vp(n,V<int>(m,-1)); int id=0; V<int>l; for (int i=0;i<h;i++) { for (int j=0;j<k;j++) { l.pb(j); } } V<P<int,int>>v; for (int i=0;i<n;i++) { int c=0; for (int j=0;j<left[i];j++) { if (val.count(x[i][j])) { vp[i][j]=0; auto it=val.find(x[i][j]); val.erase(it); c++; } else vp[i][j]=1; } for (int j=m-1;j>=right[i];j--) { if (val.count(x[i][j])) { vp[i][j]=0; auto it=val.find(x[i][j]); val.erase(it); c++; } else vp[i][j]=1; } v.pb({c,i}); } sort(all(v)); reverse(all(v)); for (int i=0;i<n;i++) { int col=v[i].S; for (int j=0;j<m;j++) { if (vp[col][j]==0) { ans[col][j]=l[id]; id++; } } } for (int i=0;i<n;i++) { set<int>st; for (int j=0;j<k;j++) { st.insert(j); } for (int j=0;j<m;j++) { if (vp[i][j]==0) { st.erase(ans[i][j]); } } for (int j=0;j<m;j++) { if (vp[i][j]==1) { ans[i][j]=*st.begin(); st.erase(ans[i][j]); } } } allocate_tickets(ans); return a; }
#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...