제출 #300412

#제출 시각아이디문제언어결과실행 시간메모리
300412easrui카니발 티켓 (IOI20_tickets)C++14
11 / 100
3095 ms768 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+m-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(); ll sum = 0; 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<m; 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] = m; } while(s<n*k/2){ if(cal(T[s].vb)==k) continue; D[T[s].vb]++; s++; } while(e>=n*m-n*k/2){ if(cal(T[e].vb)==k) continue; U[T[e].vb]--; e--; } vector<int> v(n); for(int i=0; i<k; i++){ for(int j=0; j<n; j++) v[j] = D[j]; sort(all(v)); for(int j=0; j<n; j++){ 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][U[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...