# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
301365 | 2020-09-17T21:17:11 Z | Khongor | Carnival Tickets (IOI20_tickets) | C++14 | 1322 ms | 108924 KB |
#include "tickets.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> ans; // 1 5 // 10 10 // 8 12 // 12 20 const int MAX = 1555; long long dp[MAX][MAX]; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); ans = vector<vector<int>>(n, vector<int>(m, -1)); long long res = 0; vector<pair<int, pair<int, int>>> all; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) all.push_back({x[i][j], {i, j}}); sort(all.begin(), all.end()); vector<vector<pair<int, int>>> high(n), pickedLow(n), pickedHigh(n); int median = (all[n * m / 2].first + all[n * m / 2 - 1].first) / 2; int cnt = 0; for (int i = 0; i < all.size(); i++) { int color = all[i].second.first; int ticket = all[i].second.second; if (i < all.size() / 2) { if (pickedLow[color].size() < k) { pickedLow[color].push_back({median - all[i].first, ticket}); cnt++; res += median - all[i].first; } } else { high[color].push_back({all[i].first - median, ticket}); } } for (int i = 0; i < n; i++) { while (pickedLow[i].size() + pickedHigh[i].size() < k) { res += high[i].back().first; pickedHigh[i].push_back(high[i].back()); high[i].pop_back(); } } vector<vector<long long>> b(n); int need = cnt - n * k / 2; for (int i = 0; i < n; i++) { long long s = 0; for (int j = 1; j <= min(pickedLow[i].size(), high[i].size()); j++) { s = high[i][high[i].size() - j].first - pickedLow[i][pickedLow[i].size() - j].first; b[i].push_back(s); } } vector<int> at(n, 0); while (need--) { int idx = -1, best = 0; for (int i = 0; i < n; i++) { if (at[i] == b[i].size()) continue; int cur; cur = b[i][at[i]]; if (idx == -1 || cur > best) { best = cur; idx = i; } } assert(idx != -1); // switch res += best; at[idx]++; pickedLow[idx].pop_back(); pickedHigh[idx].push_back(high[idx].back()); high[idx].pop_back(); } int cntNeg = 0, cntPos = 0; for (int i = 0; i < n; i++) { cntNeg += pickedLow[i].size(); cntPos += pickedHigh[i].size(); assert(pickedLow[i].size() + pickedHigh[i].size() == k); } assert(cntNeg + cntPos == n * k); assert(cntNeg == n * k / 2); for (int r = 0; r < k; r++) { vector<bool> used(n); vector<pair<int, int>> counts; for (int i = 0; i < n; i++) counts.push_back({pickedLow[i].size(), i}); sort(counts.rbegin(), counts.rend()); int taken = 0; for (int ii = 0; ii < n; ii++) { int i = counts[ii].second; if (pickedLow[i].size() > 0) { used[i] = true; taken++; ans[i][pickedLow[i].back().second] = r; pickedLow[i].pop_back(); } if (taken == n / 2) break; } taken = 0; for (int i = 0; i < n; i++) { if (pickedHigh[i].size() > 0 && !used[i]) { taken++; ans[i][pickedHigh[i].back().second] = r; pickedHigh[i].pop_back(); } if (taken == n / 2) break; } } allocate_tickets(ans); return res; } // a b a c // c b d d
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 1 ms | 256 KB | Output is correct |
4 | Correct | 3 ms | 640 KB | Output is correct |
5 | Correct | 40 ms | 3828 KB | Output is correct |
6 | Correct | 1006 ms | 84024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 256 KB | Contestant returned 5 while correct return value is 6. |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
3 | Correct | 1 ms | 256 KB | Output is correct |
4 | Correct | 4 ms | 640 KB | Output is correct |
5 | Correct | 48 ms | 5104 KB | Output is correct |
6 | Correct | 10 ms | 968 KB | Output is correct |
7 | Correct | 13 ms | 1472 KB | Output is correct |
8 | Correct | 1322 ms | 108924 KB | Output is correct |
9 | Correct | 1289 ms | 102244 KB | Output is correct |
10 | Correct | 1243 ms | 99328 KB | Output is correct |
11 | Correct | 1312 ms | 106452 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 640 KB | Output is correct |
3 | Correct | 4 ms | 640 KB | Output is correct |
4 | Correct | 4 ms | 640 KB | Output is correct |
5 | Correct | 5 ms | 744 KB | Output is correct |
6 | Correct | 4 ms | 640 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Incorrect | 1 ms | 384 KB | Contestant returned 160988334890 while correct return value is 160993200494. |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 3 ms | 640 KB | Output is correct |
3 | Correct | 4 ms | 640 KB | Output is correct |
4 | Correct | 4 ms | 640 KB | Output is correct |
5 | Correct | 5 ms | 744 KB | Output is correct |
6 | Correct | 4 ms | 640 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Incorrect | 1 ms | 384 KB | Contestant returned 160988334890 while correct return value is 160993200494. |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 896 KB | Output is correct |
7 | Correct | 0 ms | 256 KB | Output is correct |
8 | Correct | 0 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 256 KB | Output is correct |
10 | Correct | 3 ms | 640 KB | Output is correct |
11 | Correct | 40 ms | 3828 KB | Output is correct |
12 | Correct | 1006 ms | 84024 KB | Output is correct |
13 | Incorrect | 0 ms | 256 KB | Contestant returned 5 while correct return value is 6. |
14 | Halted | 0 ms | 0 KB | - |