oj.uz

Submission #676946

# Submission time Handle Problem Language Result Execution time Memory
676946 2023-01-01T17:25:34 Z _martynas Olympiads (BOI19_olympiads) C++11
100 / 100
 999 ms 2116 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)});
    }
    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
        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) {
                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 13 ms 340 KB Output is correct
2 Correct 10 ms 384 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 452 KB Output is correct
2 Correct 35 ms 1020 KB Output is correct
3 Correct 45 ms 1212 KB Output is correct
4 Correct 45 ms 1228 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 384 KB Output is correct
3 Correct 20 ms 320 KB Output is correct
4 Correct 17 ms 340 KB Output is correct
5 Correct 19 ms 340 KB Output is correct
6 Correct 4 ms 452 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 10 ms 384 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 452 KB Output is correct
6 Correct 35 ms 1020 KB Output is correct
7 Correct 45 ms 1212 KB Output is correct
8 Correct 45 ms 1228 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 20 ms 320 KB Output is correct
12 Correct 17 ms 340 KB Output is correct
13 Correct 19 ms 340 KB Output is correct
14 Correct 4 ms 452 KB Output is correct
15 Correct 999 ms 1140 KB Output is correct
16 Correct 269 ms 708 KB Output is correct
17 Correct 684 ms 2116 KB Output is correct
18 Correct 929 ms 1764 KB Output is correct
19 Correct 1 ms 340 KB Output is correct