제출 #301557

#제출 시각아이디문제언어결과실행 시간메모리
301557Batyr카니발 티켓 (IOI20_tickets)C++17
25 / 100
675 ms62968 KiB
#include<bits/stdc++.h> #ifndef LOCAL #include "tickets.h" #endif using namespace std; #define pb push_back #define ff first #define ss second #define sz(a) (int)a.size() typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; const ll inf=1e18; const int mod=1e9+7; const int maxn=2e3+5; int n,m,num[maxn][3],cnt[3]; int us[maxn],t,an,x; ll ans; vi b[maxn][3],d,v; vector<vector<int>>s; priority_queue<pii> g[3]; #ifdef LOCAL void allocate_tickets(vector<vi> a){ return; } #endif void f(int tp,int round){ memset(us,0,sizeof(us)); t = 0; d.clear(); while(!g[tp].empty()){ if(t == n/2) break; x=g[tp].top().ss; g[tp].pop(); us[x] = 1; num[x][tp]--; b[x][tp].pb(round); if(num[x][tp] > 0) d.pb(x); t++; } ans += t; for(auto i : d) g[tp].push({num[i][tp],i}); if(tp==1) an=0; else an=1; for(int i = 0;i < n;i++){ if(us[i] or num[i][an]==0) continue; num[i][an]--; b[i][an].pb(round); } } ll find_maximum(int k,vector<vector<int>>x){ n=sz(x); m=sz(x[0]); s.resize(n); for(int i = 0;i < n;i++) s[i].resize(m); if(m==1){ for(int i = 0;i < n;i++) v.pb(x[i][0]); sort(v.begin(),v.end()); for(int i = 0;i < n;i++) ans += abs(v[n/2]-v[i]); allocate_tickets(s); return ans; } for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++) num[i][x[i][j]]++; if(num[i][0]) g[0].push({num[i][0],i}); if(num[i][1]) g[1].push({num[i][1],i}); cnt[0] += num[i][0]; cnt[1] += num[i][1]; } for(int i = 0;i < k;i++){ if(cnt[0] < cnt[1]) f(0,i); else f(1,i); } for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(sz(b[i][x[i][j]])){ s[i][j] = b[i][x[i][j]].back(); b[i][x[i][j]].pop_back(); } else s[i][j] = -1; } } allocate_tickets(s); return ans; } #ifdef LOCAL int main(){ int n,m,k; cin >> n >> m >> k; vector<vi> c; c.resize(n); for(int i = 0;i < n;i++){ c[i].resize(m); for(int j = 0;j < m;j++) cin >> c[i][j]; } cout<<find_maximum(k,c)<<'\n'; } #endif
#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...