제출 #824685

#제출 시각아이디문제언어결과실행 시간메모리
824685thimote75카니발 티켓 (IOI20_tickets)C++14
27 / 100
564 ms73112 KiB
#include "tickets.h" #include <bits/stdc++.h> #define int long long using namespace std; using idata = vector<int>; using igrid = vector<idata>; using di = pair<int, int>; using vd = vector<di>; int find_maximum(signed K, vector<vector<signed>> x) { assert(K == 1); int N = x.size(); int M = x[0].size(); int H = N >> 1; idata minv(N, 1e16), maxv(N, -1e16); for (int i = 0; i < N; i ++) { for (int u : x[i]) { minv[i] = min(minv[i], u); maxv[i] = max(maxv[i], u); } } int result = -1; idata ub; for (int mid = 0; mid < N; mid ++) { int locr = 0; idata used_bot = { mid }; vd values; for (int i = 0; i < N; i ++) { if (i == mid) continue ; values.push_back({ minv[i] > minv[mid] ? - 1e15 : minv[mid] - minv[i], maxv[i] < minv[mid] ? - 1e15 : maxv[i] - minv[mid] }); } vd comp; int i = 0; for (const auto v : values) { if (i == mid) i ++; locr += v.second; comp.push_back({ v.first - v.second, i }); i ++; } sort(comp.rbegin(), comp.rend()); for (int i = 0; i + 1 < H; i ++) { locr += comp[i].first; used_bot.push_back(comp[i].second); } if (locr <= result) continue ; result = locr; ub.swap(used_bot); } vector<vector<signed>> allocations(N, vector<signed>(M, -1)); vector<bool> used_bot(N, false); for (int u : ub) used_bot[u] = true; for (int i = 0; i < N; i ++) { int target = used_bot[i] ? minv[i] : maxv[i]; for (int j = 0; j < M; j ++) { if (x[i][j] != target) continue ; allocations[i][j] = 0; break ; } } allocate_tickets(allocations); return result; }
#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...