Submission #834064

#TimeUsernameProblemLanguageResultExecution timeMemory
834064andrey27_smCarnival Tickets (IOI20_tickets)C++17
0 / 100
3086 ms7868 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; bool is_max[1000][1000]; set<int> a[1000]; long long find_maximum(int k, vector<vector<int>> d) { int n = d.size(); int m = d[0].size(); vector<vector<int>> ans(d.size(),vector<int>(d[0].size(),-1)); ll sum = 0; vector<pair<int,pair<int,int>>> vals; vector<int> cnt(n,0); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { vals.push_back({d[i][j],{i,j}}); a[i].insert(j); } } sort(vals.begin(),vals.end()); reverse(vals.begin(),vals.end()); int last_max = 0; for (int i = 0; i < n*k/2; ++i) { if(cnt[vals[i].second.first] == k) continue; cnt[vals[i].second.first]++; is_max[vals[i].second.first][vals[i].second.second] = 1; } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if(is_max[i][j]){ sum+=d[i][j]; a[i].erase(last_max); ans[i][j] = last_max++; last_max%=k; } } } for (int i = 0; i < n; ++i) { for (int j = 0; j+cnt[i] < k; ++j) { sum-=d[i][j]; ans[i][j] = *a[i].begin(); a[i].erase(a[i].begin()); } } allocate_tickets(ans); return sum; }
#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...