제출 #792060

#제출 시각아이디문제언어결과실행 시간메모리
792060mousebeaver카니발 티켓 (IOI20_tickets)C++14
11 / 100
434 ms57148 KiB
#define ll long long #define pll pair<ll, ll> #include "tickets.h" #include <bits/stdc++.h> using namespace std; long long find_maximum(int k, vector<vector<int>> x) { ll n = x.size(); ll m = x[0].size(); if(m == 1) { vector<vector<int>> output(n, vector<int> (1, 0)); allocate_tickets(output); vector<ll> a(n); for(ll i = 0; i < n; i++) { a[i] = x[i][0]; } sort(a.begin(), a.end()); ll ans = 0; ll add = 0; for(ll i = n/2; i >= 0; i--) { add = a[n/2] - a[i]; ans += add; } for(ll i = n/2+1; i < n; i++) { add = a[i] - a[n/2]; ans += add; } return ans; } vector<ll> zcount(n, 0); for(ll i = 0; i < n; i++) { for(ll j = 0; j < m; j++) { zcount[i] += (x[i][j] == 0); } } vector<ll> zind(n, 0); vector<ll> oind(n, 0); //Index of first zero/one vector<vector<int>> output(n, vector<int> (m, -1)); ll ans = 0; for(ll i = 0; i < k; i++) { vector<pll> zsort(n); for(ll j = 0; j < n; j++) { zsort[j] = {zcount[j], j}; } sort(zsort.begin(), zsort.end()); vector<bool> big(n, true); for(ll j = n/2; j < n; j++) { big[zsort[j].second] = false; } ll counter = 0; for(ll j = 0; j < n; j++) { if(big[j]) { //Give a one while(x[j][oind[j]] != 1) { oind[j]++; } output[j][oind[j]] = i; oind[j]++; counter++; } else { //Give a zero while(x[j][zind[j]] != 0) { zind[j]++; } output[j][zind[j]] = i; zind[j]++; zcount[j]--; } } ans += min(counter, n-counter); } allocate_tickets(output); 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...