Submission #1188339

#TimeUsernameProblemLanguageResultExecution timeMemory
1188339esomerCarnival Tickets (IOI20_tickets)C++20
0 / 100
0 ms328 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m, k; set<pair<int, int>> add0, add1; void Add0(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){ if(zeros[i] < k) add0.insert({x[i][zeros[i]] + x[i][m-ones[i]], i}); } void Add1(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){ if(zeros[i] > 0) add1.insert({x[i][zeros[i]-1] + x[i][m-ones[i]-1], i}); } void Erase0(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){ if(zeros[i] < k) add0.erase({x[i][zeros[i]] + x[i][m-ones[i]], i}); } void Erase1(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){ if(zeros[i] > 0) add1.erase({x[i][zeros[i]-1] + x[i][m-ones[i]-1], i}); } long long find_maximum(int _k, vector<vector<int>> x) { k = _k; n = (int)x.size(); m = (int)x[0].size(); vector<vector<int>> ans(n, vector<int>(m, -1)); vector<pair<int, int>> rng(n, {0, m-1}); long long res = 0; for(int r = 0; r < k; r++){ vector<pair<long long, int>> difs; for (int i = 0; i < n; i++) { difs.push_back({x[i][rng[i].second] + x[i][rng[i].first], i}); } sort(difs.begin(), difs.end()); for (int j = 0; j < n/2; j++) { int i = difs[j].second; //These substract. res -= x[i][rng[i].first]; ans[i][rng[i].first] = r; rng[i].first++; } for (int j = 0; j < n/2; j++) { int i = difs[j].second; //These add. res += x[i][rng[i].second]; ans[i][rng[i].second] = r; rng[i].second--; } } allocate_tickets(ans); return res; }
#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...