Submission #556210

#TimeUsernameProblemLanguageResultExecution timeMemory
556210sidonOlympiads (BOI19_olympiads)C++17
100 / 100
31 ms1016 KiB
#include <bits/stdc++.h> using namespace std; const int Z = 500, B = 6, MX = B * 1200; int N, K, C, s[Z][B], a[MX][B], p[MX], cur; bitset<Z> b[MX]; priority_queue<array<int, 2>> q; void process() { int u = cur++, w[K] {}; for(int j = K; j--; ) { if(a[u][j] < 0) { for(int i = N; i--; ) if(!b[u][i] && (a[u][j] < 0 || s[i][j] > s[a[u][j]][j])) a[u][j] = i; if(a[u][j] < 0) return; b[u][a[u][j]] = 1; } for(int i = K; i--; ) w[i] = max(w[i], s[a[u][j]][i]); } q.push({accumulate(w, w + K, 0), u}); } int main() { cin >> N >> K >> C; for(int i = 0; i < N; ++i) for(int j = 0; j < K; ++j) cin >> s[i][j]; fill(a[0], a[0] + K, -1); process(); while(--C) { int u = q.top()[1]; q.pop(); for(int j = K; --j >= p[u]; ) { b[cur] = b[u]; p[cur] = j; b[u][a[u][j]] = 0; a[u][j] = -1; copy(a[u], a[u] + K, a[cur]); process(); } } cout << q.top()[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...