Submission #1194180

#TimeUsernameProblemLanguageResultExecution timeMemory
1194180LucaIlieOlympiads (BOI19_olympiads)C++17
0 / 100
94 ms8772 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") #pragma GCC optimize("no-stack-protector") #endif #ifdef _MSC_VER #pragma optimize("gt", on) #pragma inline_depth(255) #pragma inline_recursion(on) #pragma comment(linker, "/STACK:20000000") #endif constexpr int MAX_N = 500; constexpr int MAX_K = 6; int n, k, c; int score[MAX_N][MAX_K]; ull putPow[MAX_K]; bitset<MAX_N> usedInTeam; int curMax[MAX_K]; struct Team { ull state; int score; bool operator<(const Team &o) const { return score < o.score; } bool operator>(const Team &o) const { return score > o.score; } }; static inline Team makeTeam(const int members[], bool calcScore) { // ensure non-decreasing for (int i = k - 1; i > 0; --i) if (members[i] < members[i - 1]) swap(const_cast<int &>(members[i]), const_cast<int &>(members[i - 1])); Team t{0, 0}; for (int i = 0; i < k; ++i) { if (calcScore) { int m = 0; for (int j = 0; j < k; ++j) m = max(m, score[members[j]][i]); t.score += m; } t.state += putPow[i] * members[i]; } return t; } static inline void unpackTeam(ull st, int members[]) { for (int i = 0; i < k; ++i) { members[i] = (st / putPow[i]) % n; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k >> c; --c; for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) cin >> score[i][j]; // precompute bases putPow[0] = 1; for (int i = 1; i < k; ++i) putPow[i] = putPow[i - 1] * n; // greedy start team int best[MAX_K]; for (int i = 0; i < k; ++i) { int pos = 0, mx = -1; for (int j = 0; j < n; ++j) { if (!usedInTeam.test(j) && score[j][i] > mx) { mx = score[j][i]; pos = j; } } usedInTeam.set(pos); best[i] = pos; } sort(best, best + k); unordered_set<ull> vis; vis.reserve(1 << 20); vis.max_load_factor(0.5f); priority_queue<Team> pq; Team start = makeTeam(best, true); pq.push(start); vis.insert(start.state); int members[MAX_K], newArr[MAX_K]; while (!pq.empty() && c-- > 0) { Team cur = pq.top(); pq.pop(); unpackTeam(cur.state, members); // prepare base (k-1) usedInTeam and curMax usedInTeam.reset(); fill(curMax, curMax + k, 0); for (int i = 0, idx = 0; i < k; ++i) { newArr[idx++] = members[i]; if (idx == k - 1) break; } for (int i = 0; i < k - 1; ++i) { int m = newArr[i]; usedInTeam.set(m); for (int j = 0; j < k; ++j) curMax[j] = max(curMax[j], score[m][j]); } int baseScore = accumulate(curMax, curMax + k, 0); // small min-heap for top-c neighbors struct Keeper { vector<Team> v; int cap; Keeper(int C) : cap(C) { v.reserve(C); } void push(const Team &t) { if ((int)v.size() < cap) { v.push_back(t); if ((int)v.size() == cap) make_heap(v.begin(), v.end(), greater<>()); } else if (t.score > v.front().score) { pop_heap(v.begin(), v.end(), greater<>()); v.back() = t; push_heap(v.begin(), v.end(), greater<>()); } } } keeper(c + 2); for (int i = 0; i < k; ++i) { // build the k-1 base excluding members[i] int idx = 0; for (int j = 0; j < k; ++j) if (j != i) newArr[idx++] = members[j]; sort(newArr, newArr + (k - 1)); // try replacing with each j not in base for (int j = 0; j < n; ++j) { if (usedInTeam.test(j)) continue; int delta = 0; for (int l = 0; l < k; ++l) if (score[j][l] > curMax[l]) delta += score[j][l] - curMax[l]; newArr[k - 1] = j; Team nb = makeTeam(newArr, false); nb.score = baseScore + delta; if (vis.insert(nb.state).second) keeper.push(nb); } } for (auto &t: keeper.v) pq.push(t); } cout << pq.top().score << "\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...