제출 #301448

#제출 시각아이디문제언어결과실행 시간메모리
301448easrui카니발 티켓 (IOI20_tickets)C++14
12 / 100
29 ms3452 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 = 85; const int MOD = 1e9+7; const ll INF = -1e18; int cur[MN],D[MN],U[MN],f[MN][MN]; int n,m; ll S[MN][MN],dp[MN][MN*MN]; bool cmp(int x, int y) { return D[x]<D[y]; } ll find_maximum(int k, vector<vector<int>> x) { n = x.size(); m = x[0].size(); ll sum = 0; vector<vector<int>> ans; vector<int> row(m,-1); for(int i=0; i<n; i++){ ans.push_back(row); } priority_queue<pii> PQ; for(int i=0; i<n; i++){ D[i] = k-1; U[i] = m; PQ.emplace(x[i][U[i]-1]+x[i][D[i]],i); } for(int i=0; i<n*k/2; i++){ int j = PQ.top().vb; PQ.pop(); U[j]--; D[j]--; if(D[j]>=0) PQ.emplace(x[j][U[j]-1]+x[j][D[j]],j); } vector<int> v(n); for(int i=0; i<k; i++){ for(int j=0; j<n; j++) v[j] = j; sort(all(v),cmp); for(int j=0; j<n; j++){ if(j>=n/2){ int c = v[j]; ans[c][D[c]] = i; sum -= x[c][D[c]]; D[c]--; } else{ int c = v[j]; ans[c][U[c]] = i; sum += x[c][U[c]]; U[c]++; } } } 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...