Submission #760539

#	Time	Username	Problem	Language	Result	Execution time	Memory
760539		Ronin13	Olympiads (BOI19_olympiads)	C++14	100 / 100	128 ms	145040 KiB

olympiads

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 501;
const int kmax = 7;

int a[nmax][kmax];
vector <bool> used(nmax);
int n, k, c;

pair<vector <int>, int> get(){
    int Ans = 0;
    vector <int> ans;
    vector <bool> used1(n + 1, false);
    for(int i = 1; i <= k; i++){
        int mx = -1;
        int mxi;
        for(int j = 1; j <= n; j++){
            if(used[j]) continue;
            if(mx < a[j][i])
                mx = a[j][i], mxi = j;
        }
        Ans += mx;
        if(used1[mxi]){
            for(int j = 1; j <= n; j++){
                if(!used1[j] && !used[j]){
                    mxi = j;
                    break;
                }
            }
        }
        if(used1[mxi]){
            return {{}, 0};
        }
        ans.pb(mxi);
        used1[mxi] = true;
    }

    return {ans, Ans};
}

vector <pair<vector <int>, int> > dq[6000001];


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> c;
    for(int i = 1; i <= n; i++){
        for(int j= 1; j <= k; j++)
            cin >> a[i][j];
    }
    int Ans = get().s;
    dq[Ans].pb({{}, 0});
    while(c--){
        while(dq[Ans].empty()) Ans--;
        vector <int> vv = dq[Ans].back().f;
        int ind = dq[Ans].back().s;
        dq[Ans].pop_back();
        for(int to : vv)
            used[to] = true;
        vector <int> o = get().f;

        for(int i = ind; i < k; i++){
            int x = o[i];
            used[x] = true;
            vector <int> u =  vv;
            u.pb(x);
            dq[get().s].pb({u, i});
            used[x] = false;
        }
        for(int to : vv)
            used[to] = false;
    }
    cout << Ans;
    return 0;
}

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