Submission #305768

#TimeUsernameProblemLanguageResultExecution timeMemory
305768bruce_testCarnival Tickets (IOI20_tickets)C++14
27 / 100
759 ms51448 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define lc (rt<<1) #define rc (rt<<1|1) #define pb push_back #define cl(a, b) memset(a, b, sizeof(a)) typedef long long ll; typedef pair<int, int> pi; typedef pair<int, pi> pii; typedef vector<int> vi; typedef vector<pi> vii; typedef vector<pii> viii; const int inf = 0x3F3F3F3F; const ll infl = 0x3F3F3F3F3F3F3F3FLL; const int mod = 1e9 + 7; void allocate_tickets(vector<vi> s); ll find_maximum(int k, vector<vi> x){ int n = x.size(), m = x[0].size(); ll ans = 0; vector<vi> s(n, vi(m, -1)); vi f(n, 0), r(n, k-1); vector<pi> p; for(int i=0; i<n; i++){ for(int j=0; j<k; j++){ ans -= x[i][j]; p.pb({x[i][j] + x[i][m-k+j], i}); } } sort(p.begin(), p.end(), greater<pi>()); for(int i=0, tot=n*k/2; i<tot; i++){ ans += p[i].f; f[p[i].s]++; r[p[i].s]--; } for(int i=0, cnt=0; i<k; i++, cnt=0){ for(int j=0; j<n; j++){ if(!f[j]) { s[j][r[j]] = i; r[j]--; } else if(r[j] == -1) { s[j][m - f[j]] = i; f[j]--; cnt++; } } for(int j=0; j<n; j++){ if(cnt < n/2) { s[j][m - f[j]] = i; f[j]--; cnt++; } else { s[j][r[j]] = i; r[j]--; } } } allocate_tickets(s); return ans; } //void allocate_tickets(vector<vi> s){ // for(int i=0; i<s.size(); i++){ // for(int x: s[i]) cout << x << " "; // cout << endl; // } //} //int main(){ // vector<vi> a = {{5, 9}, {1, 4}, {3, 6}, {2, 7}}; // cout << find_maximum(1, a) << endl; //}
#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...