Submission #417349

#TimeUsernameProblemLanguageResultExecution timeMemory
417349Aldas25Carnival Tickets (IOI20_tickets)C++14
27 / 100
632 ms53728 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define REP(n) FOR(O, 1, (n)) #define f first #define s second typedef long long ll; int mxLeft[1600]; int mxCnt[1600]; //int mnTaken[1600]; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); std::vector<std::vector<int>> answer; ll sum = 0; priority_queue<pair<ll, pair<int, int>>> q; for (int i = 0; i < n; i++) { std::vector<int> row(m); for (int j = 0; j < m; j++) { if (j >= m-k) { //row[j] = m-j-1; row[j] = -1; sum += x[i][j]; mxLeft[i]++; mxCnt[i]++; } else { row[j] = -1; } } answer.push_back(row); q.push({- x[i][0] - x[i][m-k], {i, 0}}); } REP(n*k/2) { auto p = q.top(); q.pop(); ll val = p.f; int i = p.s.f; int j = p.s.s; sum += val; mxLeft[i]--; mxCnt[i]--; // answer[i][j] = k-j-1; // answer[i][m-k+j] = -1; if (j < k-1) { j++; q.push({- x[i][j] - x[i][m-k+j], {i,j}}); } } FOR(r, 0, k-1) { int mx = n/2; FOR(i, 0, n-1) { int paimtaMax = mxCnt[i] - mxLeft[i]; int paimtaMn = r - paimtaMax; int j; if (mxLeft[i] && mx) { /// taking maximum j = m-1 - paimtaMax; mxLeft[i]--; mx--; } else { /// taking minimum j = paimtaMn; } answer[i][j] = r; } } allocate_tickets(answer); 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...