oj.uz

Submission #676949

# Submission time Handle Problem Language Result Execution time Memory
676949 2023-01-01T17:37:46 Z _martynas Olympiads (BOI19_olympiads) C++11
100 / 100
 982 ms 2060 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 340 KB Output is correct
2 Correct 11 ms 352 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 16 ms 428 KB Output is correct
2 Correct 35 ms 1108 KB Output is correct
3 Correct 45 ms 1128 KB Output is correct
4 Correct 43 ms 1200 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 1 ms 368 KB Output is correct
3 Correct 22 ms 400 KB Output is correct
4 Correct 17 ms 384 KB Output is correct
5 Correct 19 ms 384 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 14 ms 340 KB Output is correct
2 Correct 11 ms 352 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 16 ms 428 KB Output is correct
6 Correct 35 ms 1108 KB Output is correct
7 Correct 45 ms 1128 KB Output is correct
8 Correct 43 ms 1200 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 368 KB Output is correct
11 Correct 22 ms 400 KB Output is correct
12 Correct 17 ms 384 KB Output is correct
13 Correct 19 ms 384 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 982 ms 1104 KB Output is correct
16 Correct 258 ms 732 KB Output is correct
17 Correct 694 ms 2060 KB Output is correct
18 Correct 924 ms 1764 KB Output is correct
19 Correct 1 ms 340 KB Output is correct