제출 #461475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
461475		bonopo	Olympiads (BOI19_olympiads)	C++17	100 / 100	61 ms	4672 KiB

olympiads

#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 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32