Submission #1194184

#TimeUsernameProblemLanguageResultExecution timeMemory
1194184LucaIlieOlympiads (BOI19_olympiads)C++17
100 / 100
1451 ms127320 KiB
#include <bits/stdc++.h> using namespace std; using ull = unsigned long long; #if defined(__GNUC__) #pragma GCC optimize("Ofast,unroll-loops,inline,fast-math") #pragma GCC target("sse4.2,avx,avx2,bmi,bmi2,popcnt") #endif struct Node { ull st; int sc; }; struct Asc { bool operator()(Node const &a, Node const &b) const { return (a.sc < b.sc) || (a.sc == b.sc && a.st < b.st); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; long long C; cin >> N >> K >> C; static int score[500][6]; for (int i = 0; i < N; i++) for (int j = 0; j < K; j++) cin >> score[i][j]; // precompute N^i ull powN[6]; powN[0] = 1; for (int i = 1; i < K; i++) powN[i] = powN[i - 1] * (ull)N; // 1) Greedy start‐team: pick best unused per event int start[6]; { bool used[500] = {}; for (int e = 0; e < K; e++) { int bj = 0, bs = -1; for (int j = 0; j < N; j++) { if (!used[j] && score[j][e] > bs) { bs = score[j][e]; bj = j; } } used[bj] = true; start[e] = bj; } sort(start, start + K); } auto encode = [&](int a[6]) { ull s = 0; for (int i = 0; i < K; i++) s += powN[i] * (ull)a[i]; return s; }; auto fullScore = [&](int a[6]) { int tot = 0; for (int e = 0; e < K; e++) { int m = 0; for (int i = 0; i < K; i++) { int v = score[a[i]][e]; if (v > m) m = v; } tot += m; } return tot; }; // frontier: keep at most (C-iter) best candidates multiset<Node, Asc> pq; unordered_set<ull> vis; vis.reserve((size_t)C * K + 16); // seed it ull s0 = encode(start); int sc0 = fullScore(start); pq.insert({s0, sc0}); vis.insert(s0); // ← mark the start‐team visited! int cur[6], base[6], baseMax[6], newt[6]; bitset<500> in; // 2) Expand C‐1 times for (long long iter = 1; iter < C; iter++) { // pop current best auto itBest = prev(pq.end()); Node top = *itBest; pq.erase(itBest); // decode st → cur[] { ull x = top.st; for (int i = 0; i < K; i++) { cur[i] = int(x % (ull)N); x /= (ull)N; } } size_t limit = C - iter; // for each position we remove for (int rem = 0; rem < K; rem++) { // build base[0..K-2] for (int i = 0, t = 0; i < K; i++) { if (i != rem) base[t++] = cur[i]; } // compute per-event maxima & mark “in base” in.reset(); for (int e = 0; e < K; e++) baseMax[e] = 0; for (int i = 0; i < K - 1; i++) { int b = base[i]; in.set(b); for (int e = 0; e < K; e++) { int v = score[b][e]; if (v > baseMax[e]) baseMax[e] = v; } } int bs = 0; for (int e = 0; e < K; e++) bs += baseMax[e]; // try inserting any j∉base for (int j = 0; j < N; j++) { if (in.test(j)) continue; // compute delta int delta = 0; for (int e = 0; e < K; e++) { int v = score[j][e]; if (v > baseMax[e]) delta += v - baseMax[e]; } // merge j into sorted base → newt bool done = false; for (int p = 0, q = 0; p < K; p++) { if (!done && (q == K - 1 || j < base[q])) { newt[p] = j; done = true; } else { newt[p] = base[q++]; } } // encode + dedupe ull st2 = 0; for (int i = 0; i < K; i++) st2 += powN[i] * (ull)newt[i]; if (!vis.insert(st2).second) continue; Node nd{st2, bs + delta}; // bounded‐insert if (pq.size() < limit) { pq.insert(nd); } else { auto itMin = pq.begin(); if (nd.sc > itMin->sc) { pq.erase(itMin); pq.insert(nd); } } } } } // now the top is the C-th best cout << prev(pq.end())->sc << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...