Submission #1000080

#TimeUsernameProblemLanguageResultExecution timeMemory
1000080phoenixCarnival Tickets (IOI20_tickets)C++17
11 / 100
1 ms860 KiB
#include "tickets.h" #include <vector> #include <bits/stdc++.h> using namespace std; long long func(vector<int> a) { sort(a.begin(), a.end()); long long ans = 0; for (int i = 0; i < (int)a.size(); i++) { ans += (i * 2 < (int)a.size() ? -1 : +1) * a[i]; } return ans; } long long find_maximum(int k, vector<vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<vector<int>> answer(n, vector<int>(m, -1)); vector<int> l(n, 0), r(n, m - 1); long long ans = 0; for (int iter = 0; iter < k; iter++) { vector<pair<int, int>> v1, v2; for (int i = 0; i < n; i++) { v1.push_back({x[i][l[i]], i}); v2.push_back({x[i][r[i]], i}); } sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); vector<int> b1(n), b2(n); for (int i = 0; i < n; i++) { int cl; cl = v1[i].second; b1[i] = (i * 2 < n ? x[cl][l[cl]] : x[cl][r[cl]]); cl = v2[i].second; b2[i] = (i * 2 < n ? x[cl][l[cl]] : x[cl][r[cl]]); } if (func(b1) >= func(b2)) { ans += func(b1); for (int i = 0; i < n; i++) { int cl = v1[i].second; if (i * 2 < n) { answer[cl][l[cl]] = iter; l[cl]++; } else { answer[cl][r[cl]] = iter; r[cl]--; } } } else { ans += func(b2); for (int i = 0; i < n; i++) { int cl = v2[i].second; if (i * 2 < n) { answer[cl][l[cl]] = iter; l[cl]++; } else { answer[cl][r[cl]] = iter; r[cl]--; } } } } allocate_tickets(answer); 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...