Submission #1211463

#TimeUsernameProblemLanguageResultExecution timeMemory
1211463BoomydayCarnival Tickets (IOI20_tickets)C++20
100 / 100
488 ms70136 KiB
#include <bits/stdc++.h> using namespace std; #include "tickets.h" using ll = long long; /* static int n; static int m; static int k; static std::vector<std::vector<int>> d; static std::vector<std::vector<int>> x; static int called = 0; static void check(bool cond, std::string message) { if (!cond) { printf("%s\n", message.c_str()); exit(0); } } void allocate_tickets( std::vector<std::vector<int>> _d) { check(!called, "allocate_tickets called more than once"); d = _d; check((int)d.size() == n, "allocate_tickets called with parameter of wrong size"); for (int i = 0; i < n; i++) { check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size"); } called = 1; } */ long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<vector<int>> to_alloc(n, vector<int>(m, -1)); ll tot = 0; for(int i=0;i<n;++i) for(int j=0;j<k;++j) tot -= x[i][j]; vector<stack<ll>> toks(n); vector<int> pluses(n, 0), plus_a(n, m-1), minus_a(n, 0); for(int i=0;i<n;++i) for(int j=0;j<k;++j) { toks[i].push(x[i][j]+x[i][m-k+j]); } priority_queue<pair<ll,int>> pq; for(int i=0;i<n;++i) { pq.push({toks[i].top(), i}); toks[i].pop(); } for(int t=0;t<k*n/2;++t){ auto [val, i] = pq.top(); pq.pop(); pluses[i]++; tot += val; if (!toks[i].empty()) { pq.push({toks[i].top(), i}); toks[i].pop(); } } priority_queue<pair<int,int>> pq2; for(int i=0;i<n;++i) pq2.push({pluses[i], i}); vector<int> chosen(n, 0); for(int r=0;r<k;++r){ for(int i=0;i<n/2;++i){ auto [val, j] = pq2.top(); pq2.pop(); chosen[j] = 1; } for(int i=0;i<n;++i){ if (chosen[i]){ to_alloc[i][plus_a[i]--] = r; pq2.push({--pluses[i], i}); } else { to_alloc[i][minus_a[i]++] = r; } chosen[i] = 0; } } allocate_tickets(to_alloc); return tot; return tot; return 0; } /* int main() { assert(scanf("%d %d %d", &n, &m, &k) == 3); x.resize(n); for (int i = 0; i < n; i++) { x[i].resize(m); for (int j=0; j < m; j++) { assert(scanf("%d", &x[i][j]) == 1); } } fclose(stdin); long long answer = find_maximum(k, x); check(called, "failure to call allocate_tickets"); printf("%lld\n", answer); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (j) printf(" "); printf("%d", d[i][j]); } printf("\n"); } fclose(stdout); return 0; } */
#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...