oj.uz

Submission #676948

# Submission time Handle Problem Language Result Execution time Memory
676948 2023-01-01T17:36:30 Z _martynas Olympiads (BOI19_olympiads) C++11
100 / 100
 985 ms 1184 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 340 KB Output is correct
2 Correct 11 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 404 KB Output is correct
2 Correct 34 ms 604 KB Output is correct
3 Correct 43 ms 852 KB Output is correct
4 Correct 45 ms 748 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 20 ms 388 KB Output is correct
4 Correct 17 ms 392 KB Output is correct
5 Correct 20 ms 392 KB Output is correct
6 Correct 4 ms 340 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 340 KB Output is correct
2 Correct 11 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 15 ms 404 KB Output is correct
6 Correct 34 ms 604 KB Output is correct
7 Correct 43 ms 852 KB Output is correct
8 Correct 45 ms 748 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 20 ms 388 KB Output is correct
12 Correct 17 ms 392 KB Output is correct
13 Correct 20 ms 392 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 985 ms 696 KB Output is correct
16 Correct 259 ms 536 KB Output is correct
17 Correct 695 ms 1184 KB Output is correct
18 Correct 934 ms 996 KB Output is correct
19 Correct 2 ms 340 KB Output is correct