Submission #676949

#	Time	Username	Problem	Language	Result	Execution time	Memory
676949		_martynas	Olympiads (BOI19_olympiads)	C++11	100 / 100	982 ms	2060 KiB

olympiads

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

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, vi>> PQ;
    set<vi> visited;
    {
        int val = 0; for(int i = 0; i < k; i++) val += B[i][0];
        visited.insert(vi(k));
        PQ.push({val, vi(k)});
    }
    // how many ways to cover each subset of {0, 1, ..., k-1} using set num of elements
    ll dp[2][k+1][1<<k];
    while(!PQ.empty() && c > 0) {
        int curr_val = PQ.top().F;
        vi ids = PQ.top().S; PQ.pop();

//        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
        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) {
                int val = 0; for(int j = 0; j < k; j++) val += B[j][new_ids[j]];
                if(!visited.count(new_ids)) {
                    visited.insert(new_ids);
                    PQ.push({val, new_ids});
                }
            }
        }
    }

    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