제출 #1008051

#제출 시각아이디문제언어결과실행 시간메모리
1008051Mizo_Compiler카니발 티켓 (IOI20_tickets)C++17
11 / 100
2 ms1080 KiB
#include <bits/stdc++.h> using namespace std; #include "tickets.h" typedef long long ll; #define F first #define S second #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define pb push_back const int N = 1505; int tk[N], n, m, k; vector<vector<int>> a; vector<int> vv[N], vv2[N]; ll gt(int id) { if (tk[id] == k)return 1e18; return (a[id][k-1-tk[id]] + a[id][m-1-tk[id]]); } ll find_maximum(int ko, vector<vector<int>> xx) { a = xx; n = sz(a); m = sz(a[0]); k = ko; a = xx; ll ans = 0; set<pair<ll, int>> s; for (int i = 0; i < n; i++) { tk[i] = 0; vv[i].clear(); vv2[i].clear(); sort(all(a[i]), greater<>()); for (int j = 0; j < k; j++) { ans += a[i][j]; } s.insert({gt(i), i}); } int cnt = (n >> 1) * k; while (cnt--) { ll x = s.begin()->F; int i = s.begin()->S; s.erase(s.begin()); ans -= x; ++tk[i]; s.insert({gt(i), i}); } vector<vector<int>> res(n, vector<int> (m, -1)); for (int i = 0; i < n; i++) { for (int j = 0; j <= k-1-tk[i]; j++) { vv[i].pb(j); } for (int j = m-1; j > m-1-tk[i]; j--) { vv2[i].pb(j); } } for (int ii = 0; ii < k; ii++) { vector<pair<int, int>> vo; for (int i = 0; i < n; i++)vo.pb({sz(vv[i]), i}); sort(all(vo)); for (int i = 0; i < n; i++) { int cur = vo[i].S; if (vv[cur].empty() || (i < n/2 && !vv2[cur].empty())) { res[cur][vv2[cur].back()] = ii; vv2[cur].pop_back(); } else { res[cur][vv[cur].back()] = ii; vv[cur].pop_back(); } } } allocate_tickets(res); return ans; } /*int main() { int nn, mm, kk; cin >> nn >> mm >> kk; vector<vector<int>> vvv(nn, vector<int>(mm)); for (int i = 0; i < nn; i++) { for (int j = 0; j < mm; j++) { cin >> vvv[i][j]; } } cout << find_maximum(kk, vvv); }*/
#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...