Submission #1036446

#TimeUsernameProblemLanguageResultExecution timeMemory
1036446Mr_HusanboyCarnival Tickets (IOI20_tickets)C++17
25 / 100
297 ms57684 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define all(a) (a).begin(), (a).end() template<typename T> int len(T &a){ return a.size(); } mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<vector<int>> ans(n, vector<int>(m, -1)); vector<int> v; vector<int> cnt(n); for(int i = 0; i < n; i ++){ for(int j = 0; j < m; j ++){ cnt[i] += x[i][j]; } } vector<int> l(n, 0), r(n, m - 1); ll mx = 0; vector<int> ind(n); iota(all(ind), 0); for(int lev = 0; lev < k; lev ++){ sort(all(ind), [&](int i, int j){return cnt[i] < cnt[j];}); vector<int> v(n); for(int _ = 0; _ < n / 2; _ ++){ int i = ind[_]; v[i] = x[i][l[i]]; ans[i][l[i]] = lev; cnt[i] -= v[i]; //cout << i << ' '; l[i] ++; } for(int _ = n / 2; _ < n; _ ++){ int i = ind[_]; v[i] = x[i][r[i]]; ans[i][r[i]] = lev; cnt[i] -= v[i]; r[i] --; } sort(all(v)); for(int i = 0; i < n; i ++){ mx += abs(v[i / 2] - v[i]); } } allocate_tickets(ans); return mx; }
#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...