Submission #1225299

#TimeUsernameProblemLanguageResultExecution timeMemory
1225299NonozeCarnival Tickets (IOI20_tickets)C++20
11 / 100
2 ms840 KiB
#include "tickets.h" #include <bits/stdc++.h> #define fi first #define se second #define sz(x) (int)x.size() #define cmin(a, b) a=min(a, b) #define cmax(a, b) a=max(a, b) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define pb push_back #define int long long using namespace std; int n, m, k; vector<vector<int>> a; int find_maximum(signed K, vector<vector<signed>> x) { n=sz(x), m=sz(x[0]), k=K; a.resize(n, vector<int>(m)); for (int i=0; i<n; i++) for (int j=0; j<m; j++) a[i][j]=x[i][j]; vector<pair<vector<int>, vector<int>>> empl(n); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (a[i][j]) empl[i].se.pb(j); else empl[i].fi.pb(j); } } int res=0; vector<vector<signed>> ans(n, vector<signed>(m, -1)); if (m==1) { ans.clear(), ans.resize(n, vector<signed>(m, 0)); allocate_tickets(ans); vector<int> b; for (int i=0; i<n; i++) b.pb(a[i][0]); sort(all(b)); for (int i=0; i<n/2; i++) res+=b[n-i-1]-b[i]; return res; } vector<int> vec(n); for (int i=0; i<n; i++) for (int j=0; j<m; j++) vec[i]+=a[i][j]; for (int t=0; t<k; t++) { int left=m-t; vector<pair<int, int>> temp; for (int i=0; i<n; i++) temp.pb({vec[i], i}); sort(all(vec)); int nb0=0, nb1=0; for (int i=0; i<n/2; i++) { if (left-temp[i].fi) { nb0++; ans[i][empl[i].fi.back()]=t; empl[i].fi.pop_back(); } else { nb1++, vec[i]--; ans[i][empl[i].se.back()]=t; empl[i].se.pop_back(); } } for (int i=n/2; i<n; i++) { if (temp[i].fi) { nb1++, vec[i]--; ans[i][empl[i].se.back()]=t; empl[i].se.pop_back(); } else { nb0++; ans[i][empl[i].fi.back()]=t; empl[i].fi.pop_back(); } } res+=min(nb0, nb1); } 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...