Submission #834827

#TimeUsernameProblemLanguageResultExecution timeMemory
834827JohannCarnival Tickets (IOI20_tickets)C++14
27 / 100
481 ms75796 KiB
#include "tickets.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; typedef vector<pii> vpii; typedef vector<vpii> vvpii; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() long long find_maximum(int K, std::vector<std::vector<int>> x) { int N = x.size(); int M = x[0].size(); ll value = 0; vvi ans(N, vi(M, -1)); vvi mapping(N, vi(M, -1)); // mapping of pairs vvpii gains(N); for (int i = 0; i < N; ++i) { vpii A(M); for (int j = 0; j < M; ++j) A[j] = {x[i][j], i * M + j}; sort(all(A)); int delta = M - K; for (int j = 0; j < K; ++j) { value -= A[j].first; ans[i][A[j].second % M] = -2; // i use it as a negative mapping[i][A[j + delta].second % M] = A[j].second % M; gains[i].push_back({A[j].first + A[j + delta].first, A[j + delta].second}); } sort(all(gains[i])); } for (int k = 0; k < K; ++k) { priority_queue<pii, vpii> q; for (int i = 0; i < N; ++i) q.push(gains[i].back()); for (int l = 0, i, j; l < N / 2; ++l) { pii tmp = q.top(); q.pop(); i = tmp.second / M, j = tmp.second % M; gains[i].pop_back(); value += tmp.first; ans[i][mapping[i][j]] = -1; ans[i][j] = k; } } for (int i = 0; i < N; ++i) { vi values(M); for (int j = 0; j < M; ++j) values[j] = ans[i][j]; sort(all(values)); int k = K - 1; for (int j = 0; j < M; ++j) if (ans[i][j] == -2) { while (k == values.back()) values.pop_back(), --k; ans[i][j] = k--; } } allocate_tickets(ans); return value; }
#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...