Submission #648526

#	Time	Username	Problem	Language	Result	Execution time	Memory
648526		Lobo	Olympiads (BOI19_olympiads)	C++17	100 / 100	649 ms	96536 KiB

olympiads

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2020;

int n,k,c, a[maxn][maxn], ch[maxn][maxn];
vector<pair<int,int>> pts[maxn];

void solve() {
    cin >> n >> k >> c;
    for(int i = 1; i <= n; i++) {
         for(int j = 0; j < k; j++) {
            cin >> a[i][j];
            pts[j].pb(mp(a[i][j],i));
         }
    }

    for(int i = 0; i <= n; i++) {
        ch[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            ch[i][j] = ch[i-1][j-1]+ch[i-1][j];
            ch[i][j] = min(ch[i][j],c);
        }
    }

    map<vector<int>,int> anst;
    for(int j = 0; j < k; j++) {
        sort(all(pts[j]),greater<pair<int,int>>());
    }
    
    priority_queue<pair<int,vector<int>>> pq;
    map<vector<int>,int> pt;
    vector<int> vbeg,vids;
    int pbeg = 0;
    for(int j = 0; j < k; j++) {
        vbeg.pb(0);
        pbeg+= pts[j][0].fr;
    }

    pq.push(mp(pbeg,vbeg));
    pt[vbeg] = pbeg;

    while(true) {
        vector<int> v = pq.top().sc;
        pq.pop();

        bool okk = true;
        for(int j = 0; j < k; j++) {
            for(int i = 0; i < k; i++) {
                int id = pts[i][v[i]].sc;
                if(mp(a[id][j],id) > pts[j][v[j]]) {
                    okk = false;
                }
            }
        }
        // if(!okk) {
        //     for(int i = 0; i < k; i++) {
        //         cout << pts[i][v[i]].sc << " ";
        //     }cout << endl;
        //     for(int i = 0; i < k; i++) {
        //         cout << v[i] << " ";
        //     }cout << endl;
        //     cout << pt[v] << endl;
        //     continue;
        // }

        if(okk) {
            set<int> fq;
            for(int j = 0; j < k; j++) {
                fq.insert(pts[j][v[j]].sc);
            }
            int qtd = 0;
            for(int i = 1; i <= n; i++) {
                int ok = 1;
                for(int j = 0; j < k; j++) {
                    if(mp(a[i][j],i) >= pts[j][v[j]]) ok = 0;
                }
                qtd+= ok;
            }

            c-= ch[qtd][k-fq.size()]; //ways to do this = choose(qtd,k-fq.size())

            // for(int i = 0; i < k; i++) {
            //     cout << pts[i][v[i]].sc << " ";
            // }cout << endl;
            // for(int i = 0; i < k; i++) {
            //     cout << v[i] << " ";
            // }cout << endl;
            // cout << pt[v] << endl;
            // cout << ch[qtd][k-fq.size()] << " " << qtd << " " << k-fq.size() << endl << endl;
            if(c <= 0) {
                cout << pt[v] << endl;
                return;
            }
        }

        for(int j = 0; j < k; j++) {
            if(v[j] != n-1) {
                v[j]++;
                if(pt.count(v)) {
                    v[j]--;
                    continue;
                }
                int p1 = 0;
                for(int i = 0; i < k; i++) {
                    p1+= pts[i][v[i]].fr;
                }
                pt[v] = p1;
                pq.push(mp(pt[v],v));
                v[j]--;

                // cout << "  " << j << " " << p1 << endl;
            }
        }
    }

    // while(pq.size() && qtdc <= c) {
    //     vector<int> v = pq.top().sc;
    //     int p = pq.top().fr;
    //     pq.pop();
    //     qtdc++;
    //     vector<int> vt;
    //     for(auto x : v) {
    //         vt.pb(pts[j][x].sc);
    //     }
    //     sort(all(vt));
    //     anst[vt] = max(anst[vt],p);
    //     for(int i = 0; i < k; i++) {
    //         if(i < k-1 && v[i]+1 == v[i+1]) continue;
    //         if(i == k+1 && v[i] == n-1) continue;
    //         vector<int> v1 = v;
    //         v1[i]++;
    //         if(pt.count(v1)) continue;
    //         int p1 = 0;
    //         for(int i1 = 0; i1 < k; i1++) {
    //             p1+= pts[j][i1].fr;
    //         }
    //         pt[v1] = p1;
    //         pq.push(mp(p1,v1));
    //     }
    // }
    

    // vector<int> ans;
    // for(auto X : anst) {
    //     ans.pb(X.sc);
    // }
    // sort(all(ans));
    // cout << ans[c-1] << endl;


}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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