제출 #300376

#제출 시각아이디문제언어결과실행 시간메모리
300376easrui카니발 티켓 (IOI20_tickets)C++14
0 / 100
1 ms512 KiB
#include "tickets.h" #include <bits/stdc++.h> #define va first #define vb second #define all(x) (x).begin(), (x).end() using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<pii,int> ppi; typedef pair<int,pii> pip; const int MN = 1505; const int MOD = 1e9+7; const int INF = 1e9; vector<pii> T; int a[MN],s[MN],cur[MN],D[MN],U[MN]; int n,m; int cal(int x) { return D[x]+1+n-U[x]; } bool cmp(int x, int y) { return s[x]<s[y]; } ll find_maximum(int k, vector<vector<int>> x) { n = x.size(); m = x[0].size(); vector<vector<int>> ans; vector<int> row(m,-1); for(int i=0; i<n; i++){ ans.push_back(row); } for(int i=0; i<n; i++) for(int j=0; j<n; j++) T.emplace_back(x[i][j],i); sort(all(T)); int s=0, e=n*m-1; for(int i=0; i<n; i++){ D[i] = -1; U[i] = n; } while(s<n*k/2){ D[T[s].vb]++; s++; } while(e>=n*(m-k)/2){ U[T[e].vb]--; e--; } int cnt = 0; priority_queue<pip> PQ; for(int i=0; i<n; i++){ PQ.emplace(cal(i),pii{i,++cnt}); cur[i] = cnt; } while(PQ.top().va>k){ int q = PQ.top().vb.vb; if(T[s].va-D[q]<U[q]-T[e].va){ D[q]--; PQ.emplace(cal(q),pii{q,++cnt}); cur[q] = cnt; D[T[s].vb]++; PQ.emplace(cal(T[s].vb),pii{T[s].vb,++cnt}); cur[T[s].vb] = cnt; s++; } else{ U[q]++; PQ.emplace(cal(q),pii{q,++cnt}); cur[q] = cnt; U[T[e].vb]--; PQ.emplace(cal(T[e].vb),pii{T[e].vb,++cnt}); cur[T[e].vb] = cnt; e--; } while(PQ.top().vb.vb!=cur[PQ.top().vb.va]) PQ.pop(); } ll sum = 0; for(int i=0; i<k; i++){ vector<int> v; for(int j=0; j<n; i++) v.push_back(D[j]); sort(all(v)); for(int j=0; j<n; j++){ vector<int> v; if(D[j]>=v[n/2]){ ans[j][D[j]] = i; sum -= x[j][D[j]]; D[j]--; } else{ ans[j][U[j]] = i; sum += x[j][D[j]]; U[j]++; } } } allocate_tickets(ans); 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...