Submission #461445

#	Time	Username	Problem	Language	Result	Execution time	Memory
461445		bonopo	Olympiads (BOI19_olympiads)	C++17	44 / 100	11 ms	972 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], bst[6], 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; }
};
//
//struct pqcmp {
//    bool cmp(crack a, crack b)
//};
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 i=0; i<sel.size(); ++i) use[sel[i]]=1, all.pb(sel[i]);
    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 crack((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.pb(c.all[i]);
            pq.push(gen(sel, dnt));
        }
    }
}

// MM

Compilation message (stderr)

olympiads.cpp: In function 'crack gen(std::vector<int>, std::vector<int>)':
olympiads.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0; i<sel.size(); ++i) use[sel[i]]=1, all.pb(sel[i]);
      |                  ~^~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32