Submission #676948

#	Time	Username	Problem	Language	Result	Execution time	Memory
676948		_martynas	Olympiads (BOI19_olympiads)	C++11	100 / 100	985 ms	1184 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 505;
const int MXK = 7;

int n, k, c;
ll A[MXK][MXN];
ll B[MXK][MXN];

int main() {
    FASTIO();

    cin >> n >> k >> c;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) {
            cin >> A[j][i]; B[j][i] = A[j][i];
        }
    }

    //cerr << "-------------\n";
    for(int i = 0; i < k; i++) sort(B[i], B[i]+n), reverse(B[i], B[i]+n);
//    for(int i = 0; i < n; i++) {
//        for(int j = 0; j < k; j++) {
//            cerr << B[j][i] << " ";
//        }
//        cerr << "\n";
//    }

    priority_queue<pair<int, ll>> PQ;
    set<ll> visited;
    {
        int val = 0;
        ll key = 0;
        for(int i = 0; i < k; i++) {
            val += B[i][0];
            key = key * MXN + 1;
        }
        PQ.push({val, key});
    }
    while(!PQ.empty() && c > 0) {
        int curr_val = PQ.top().F;
        vi ids;
        ll curr_key = PQ.top().S; PQ.pop();
        for(int i = 0; i < k; i++) {
            ids.PB(curr_key % MXN - 1);
            curr_key /= MXN;
        }
        reverse(ids.begin(), ids.end());

//        cerr << "-----------\n";
//        cerr << curr_val << ", c = " << c << "\n";
//        for(int i = 0; i < k; i++) cerr << ids[i] << " ";
//        cerr << "\n";
//        for(int i = 0; i < k; i++) cerr << B[i][ids[i]] << " ";
//        cerr << "\n";

        ll cnt = 0; // how many different teams can have maximum equal to B[k][ids[k]] for each k?
        // bitmask dp
        ll dp[2][k+1][1<<k]; // how many ways to cover each subset of {0, 1, ..., k-1} using set num of elements
        int from = 0, to = 1;
        memset(dp[from], 0, sizeof(dp[from]));
        dp[from][0][0] = 1;
        for(int i = 0; i < n; i++) {
            memset(dp[to], 0, sizeof(dp[to]));
            int b_i = 0;
            bool bad = false;
            for(int j = 0; j < k; j++) {
                if(A[j][i] > B[j][ids[j]]) bad = true; // can't take higher value
                if(A[j][i] == B[j][ids[j]]) b_i |= 1 << j;
            }
            if(bad) continue;
            for(int b = 0; b < (1<<k); b++) {
                int b_to = b|b_i;
                for(int u = 1; u <= k; u++) {
                    dp[to][u][b_to] += dp[from][u-1][b];
                }
            }
            for(int b = 0; b < (1<<k); b++) {
                for(int u = 0; u <= k; u++) {
                    dp[to][u][b] += dp[from][u][b]; // don't take i-th
                }
            }
            swap(from, to);
        }
        cnt = dp[from][k][(1<<k)-1];
        //cerr << cnt << "!\n";

        if(c - cnt <= 0) {
            cout << curr_val << "\n";
            return 0;
        }
        c -= cnt;
        for(int i = 0; i < k; i++) {
            vi new_ids = ids;
            while(new_ids[i]<n && B[i][ids[i]] == B[i][new_ids[i]]) new_ids[i]++;
            if(new_ids[i]+k-1<n) {
                ll key = 0;
                int val = 0;
                for(int j = 0; j < k; j++) {
                    val += B[j][new_ids[j]];
                    key = key * MXN + (new_ids[j]+1);
                }
                if(!visited.count(key)) {
                    visited.insert(key);
                    PQ.push({val, key});
                }
            }
        }
    }

    return 0;
}

/*
5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9

1 1 1
1


*/

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