제출 #774040

#제출 시각아이디문제언어결과실행 시간메모리
774040kingfran1907카니발 티켓 (IOI20_tickets)C++14
11 / 100
5 ms6740 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; typedef long long llint; const int maxn = 1510; int n, m, k; llint pref[maxn][maxn]; int t[maxn]; int ptrl[maxn], ptrr[maxn]; bool bio[maxn]; llint f(int x, int t) { return pref[x][m] - pref[x][m - t] - pref[x][k - t]; } llint cal(int x, int t) { if (t == 0) return (1LL << 60); return f(x, t) - f(x, t - 1); } long long find_maximum(int K, std::vector<std::vector<int>> x) { n = x.size(); m = x[0].size(); k = K; vector< vector<int> > ans(n, vector<int>(m, -1)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) pref[i][j + 1] = pref[i][j] + x[i][j]; set< pair<llint, int> > s; for (int i = 0; i < n; i++) { t[i] = k; s.insert({cal(i, k), i}); } for (int abc = 0; abc < k * n / 2; abc++) { auto iter = s.begin(); int ind = iter->second; s.erase(iter); t[ind]--; s.insert({cal(ind, t[ind]), ind}); } //for (int i = 0; i < n; i++) printf("%d ", t[i]); //printf("\n"); llint sol = 0; for (int i = 0; i < n; i++) sol += f(i, t[i]); for (int i = 0; i < n; i++) { ptrr[i] = 0, ptrr[i] = m - 1; } int mid = n / 2; for (int i = 0; i < k; i++) { vector< pair<int, int> > v; for (int j = 0; j < n; j++) { v.push_back({x[j][ptrl[j]], j}); } sort(v.begin(), v.end()); for (int j = 0; j < n; j++) { int x = v[j].second; if (j < mid) { ans[x][ptrl[x]++] = i; } else { ans[x][ptrr[x]--] = i; } } } allocate_tickets(ans); return sol; }
#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...