Submission #1225790

#TimeUsernameProblemLanguageResultExecution timeMemory
1225790The_SamuraiCarnival Tickets (IOI20_tickets)C++17
27 / 100
305 ms51360 KiB
#include "tickets.h" #include "bits/stdc++.h" using namespace std; using ll = long long; const ll inf = 1e18; long long find_maximum(int k, std::vector<std::vector<int>> a) { int n = a.size(); int m = a[0].size(); vector<int> pos(n); vector vec(n, vector(m, -1)); ll ans = 0; for (int i = 0; i < n; i++) for (int j = m - k; j < m; j++) ans += a[i][j]; priority_queue<pair<ll, int>> pq; for (int i = 0; i < n; i++) pq.emplace(-a[i][0] - a[i][m - k], i); for (int shit = 0; shit < n * k / 2; shit++) { auto [d, i] = pq.top(); pq.pop(); ans += d; pos[i]++; if (pos[i] < k) pq.emplace(-a[i][pos[i]] - a[i][m - (k - pos[i])], i); } for (int i = 0; i < n; i++) for (int j = 0; j < pos[i]; j++) vec[i][j] = j; for (int i = 0; i < n; i++) { int z = pos[i]; for (int j = m - (k - pos[i]); j < m; j++) vec[i][j] = z++; } ll exp = 0; vector<vector<int>> shit(k); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) if (vec[i][j] != -1) shit[vec[i][j]].emplace_back(a[i][j]); } for (auto v: shit) { sort(v.begin(), v.end()); for (int x: v) exp += abs(x - v[n / 2]); } assert(exp == ans); allocate_tickets(vec); return ans; }
#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...