Submission #1000090

#TimeUsernameProblemLanguageResultExecution timeMemory
1000090phoenixCarnival Tickets (IOI20_tickets)C++17
27 / 100
321 ms73216 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<bool> t(n, false); long long val = 0; vector<int> ord(n); for (int i = 0; i < n; i++) { val += -x[i][l[i]]; ord[i] = i; } sort(ord.begin(), ord.end(), [&](int a, int b) { return (x[a][l[a]] + x[a][r[a]]) > (x[b][l[b]] + x[b][r[b]]); }); for (int i = 0; i * 2 < n; i++) { int j = ord[i]; val += x[j][l[j]] + x[j][r[j]]; t[j] = true; } ans += val; for (int i = 0; i < n; i++) { if (t[i]) { answer[i][r[i]] = iter; r[i]--; } else { answer[i][l[i]] = iter; l[i]++; } } } 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...