제출 #565901

#제출 시각아이디문제언어결과실행 시간메모리
565901sidon카니발 티켓 (IOI20_tickets)C++17
25 / 100
820 ms127484 KiB
#include "tickets.h" #include "bits/stdc++.h" using namespace std; using ll = long long; ll find_maximum(int k, vector<vector<int>> x) { int n = x.size(), m = x[0].size(); vector<vector<int>> g(n, vector<int> (m, -1)); ll res {}; vector<array<ll, 3>> a; int b[n]; for(int i = n; i--; ) { b[i] = k; ll cur {}; for(int j = 0; j < k; ++j) cur -= x[i][j]; res += cur; for(int j = k; j--; ) { ll add = x[i][j] + x[i][m+j-k]; a.push_back({add, i, j}); cur += add; } } sort(begin(a), end(a)); for(int i = size(a); --i >= (k * n / 2); ) { res += a[i][0]; b[a[i][1]] = a[i][2]; } for(int i = n; i--; ) { for(int j = b[i]; j--; ) --g[i][j]; for(int j = 0; j < k - b[i]; ++j) ++g[i][m-1-j]; } int l[n] {}, r[n]; bool vis[n]; fill(r, r + n, m-1); for(int c = 0; c < k; ++c) { int cnt {}; fill(vis, vis + n, 0); for(int i = n; i--; ) { if(g[i][l[i]] > -2) g[i][r[i]--] = c, ++cnt, vis[i] = 1; if(g[i][r[i]] < 0) g[i][l[i]++] = c, --cnt, vis[i] = 1; } for(int i = n; i--; ) if(!vis[i]) { if(cnt < 0) g[i][r[i]--] = c, ++cnt; else g[i][l[i]++] = c, --cnt; } } allocate_tickets(g); 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...