제출 #1096070

#제출 시각아이디문제언어결과실행 시간메모리
1096070MateiKing80Olympiads (BOI19_olympiads)C++14
100 / 100
19 ms3120 KiB
#include<bits/stdc++.h> using namespace std; int n, k, i, j, nr, c, x; int a[505][7], curr[505]; struct ura { int scor, sol[7]; char f[505]; }; ura h[12005]; void calc(ura &x) { int i, ind, j, maxim; memset(curr, 0, sizeof(curr)); for(i = 1; i <= k; i ++) { ind = x.sol[i]; if(x.f[ind] != 2) break; } for(; i <= k; i ++) { maxim = -1; ind = -1; for(j = 1; j <= n; j ++) if(x.f[j] == 0 && curr[j] == 0 && a[j][i] > maxim) { maxim = a[j][i]; ind = j; } if(ind == -1) { x.scor = -1000000000; return; } curr[ind] = 1; x.sol[i] = ind; } x.scor = 0; for(i = 1; i <= k; i++) { maxim = 0; for(j = 1; j <= k; j++) maxim = max(maxim, a[ x.sol[j] ][i]); x.scor += maxim; } } void upd(int c) { int p = c / 2; while(p > 0 && h[p].scor < h[c].scor) { swap(h[p], h[c]); c = p; p = c / 2; } } void elim() { int p = 1, c = 2; while(c <= nr) { if(c + 1 <= nr && h[c + 1].scor > h[c].scor) c ++; if(h[c].scor > h[p].scor) { swap(h[p], h[c]); p = c; c = 2 * p; } else break; } } int main() { cin>> n >> k >> c; for(i = 1; i <= n; i ++) for(j = 1; j <= k; j ++) cin >> a[i][j]; nr = 1; calc(h[1]); for(; c > 1; c --) { for(j = 1; j <= k; j ++) if(h[1].f[h[1].sol[j] ] != 2) break; for(; j <= k; j ++) { x = h[1].sol[j]; h[1].f[x] = 1; h[++ nr] = h[1]; calc(h[nr]); upd(nr); h[1].f[x] = 2; } swap(h[1], h[nr]); nr --; elim(); } cout << h[1].scor; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...