oj.uz

Submission #461475

# Submission time Handle Problem Language Result Execution time Memory
461475 2021-08-10T02:40:12 Z bonopo Olympiads (BOI19_olympiads) C++17
100 / 100
 61 ms 4672 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=505, MOD=1e9+7, LOG=19;
int N, K, C, use[MM], bad[MM], s[MM][6];

struct crack {
    int cost;
    vector<int> all, sel, dnt;
    crack(int _cost, vector<int> _all, vector<int> _sel, vector<int> _dnt) {
        cost=_cost; all=_all; sel=_sel; dnt=_dnt; }
    bool operator < (crack oth) const { return cost < oth.cost; }
}; priority_queue<crack> pq;

crack gen(vector<int> sel, vector<int> dnt) {
    vector<int> all; int cost=0, n=0;
    for(int &e:dnt) bad[e]=1;
    for(int &e:sel) use[e]=1, all.pb(e);
    for(int i=sel.size(); i<K; ++i) {
        all.pb(N);
        for(int j=0; j<N; ++j) if(!bad[j]&&!use[j]) {
            if(s[j][i]>=s[all[i]][i]) all[i]=j; }
        use[all[i]]=1; n+=(all[i]==N); }
    for(int &e:dnt) bad[e]=0;
    for(int i=0, mx=0; i<K; ++i, mx=0) {
        for(int &e:all) mx=max(mx, s[e][i]), use[e]=0;
        cost+=mx; }
    return {(int)(n?-1e9:cost), all, sel, dnt};
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N>>K>>C;
    for(int i=0; i<N; ++i) for(int k=0; k<K; ++k) cin>>s[i][k];
    pq.push(gen({}, {}));
    while(C--) {
        assert(pq.size());
        crack c=pq.top(); pq.pop();
        if(!C) return cout<<c.cost<<el, 0;
        vector<int> dnt=c.dnt, sel=c.sel;
        for(int i=c.sel.size(); i<K; sel.pb(c.all[i]), ++i, dnt.pop_back()) {
            dnt.pb(c.all[i]);
            pq.push(gen(sel, dnt));
        }
    }
}

// MM

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 588 KB Output is correct
2 Correct 10 ms 460 KB Output is correct
3 Correct 11 ms 460 KB Output is correct
4 Correct 8 ms 460 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 552 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 12 ms 900 KB Output is correct
4 Correct 9 ms 668 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 408 KB Output is correct
2 Correct 9 ms 636 KB Output is correct
3 Correct 34 ms 1600 KB Output is correct
4 Correct 37 ms 2036 KB Output is correct
5 Correct 31 ms 2720 KB Output is correct
6 Correct 9 ms 588 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 588 KB Output is correct
2 Correct 10 ms 460 KB Output is correct
3 Correct 11 ms 460 KB Output is correct
4 Correct 8 ms 460 KB Output is correct
5 Correct 8 ms 552 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Correct 12 ms 900 KB Output is correct
8 Correct 9 ms 668 KB Output is correct
9 Correct 10 ms 408 KB Output is correct
10 Correct 9 ms 636 KB Output is correct
11 Correct 34 ms 1600 KB Output is correct
12 Correct 37 ms 2036 KB Output is correct
13 Correct 31 ms 2720 KB Output is correct
14 Correct 9 ms 588 KB Output is correct
15 Correct 11 ms 504 KB Output is correct
16 Correct 26 ms 1416 KB Output is correct
17 Correct 61 ms 4672 KB Output is correct
18 Correct 21 ms 916 KB Output is correct
19 Correct 9 ms 644 KB Output is correct