Submission #124973

#	Time	Username	Problem	Language	Result	Execution time	Memory
124973		songc	Olympiads (BOI19_olympiads)	C++14	13 / 100	193 ms	3068 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, K;
int A[7][550];
int R[7][7][550];
LL C, D[7][70][550];
int mask[550];
bool chk[550];
vector<LL> comp[7];

struct Data{
    LL sum;
    int v[7];
    bool operator<(const Data &r)const{
        if (sum == r.sum){
            for (int i=1; i<=K; i++) if (v[i] != r.v[i]) return v[i] < r.v[i];
            return false;
        }
        return sum < r.sum;
    }
};

priority_queue<Data> PQ;
set<Data> vis;

int main(){
    scanf("%d %d %lld", &N, &K, &C);
    for (int i=1; i<=N; i++) for (int j=1; j<=K; j++){
        scanf("%d", &A[j][i]);
        comp[j].push_back(A[j][i]);
    }
    for (int i=1; i<=K; i++) {
        sort(comp[i].begin(), comp[i].end(), greater<LL>());
        comp[i].erase(unique(comp[i].begin(), comp[i].end()), comp[i].end());
        for (int j=1; j<=N; j++) A[i][j] = lower_bound(comp[i].begin(), comp[i].end(), A[i][j], greater<LL>()) - comp[i].begin();
    }
    memset(R, 15, sizeof R);
    for (int i=1; i<=N; i++) for (int j=1; j<=K; j++) for (int k=1; k<=K; k++) R[j][k][A[j][i]] = min(A[k][i], R[j][k][A[j][i]]);
    Data T;
    T.sum = 0;
    for (int i=1; i<=K; i++) T.v[i] = 0, T.sum += comp[i][0];
    PQ.push(T);
    while (!PQ.empty()){
        T = PQ.top();
        PQ.pop();

        for (int i=1; i<=N; i++){
            mask[i] = 0, chk[i] = false;
            for (int j=1; j<=K; j++){
                if (T.v[j] == A[j][i]) mask[i] |= 1<<(j-1);
                if (T.v[j] > A[j][i]) chk[i] = true;
            }
        }

        memset(D, 0, sizeof D);
        D[0][0][0] = 1;
        for (int i=0; i<N; i++){
            for (int j=0; j<=K; j++){
                for (int k=0; k<(1<<K); k++){
                    if (!D[j][k][i]) continue;
                    D[j][k][i+1] += D[j][k][i];
                    if (j<6 && !chk[i+1]) D[j+1][k|mask[i+1]][i+1] += D[j][k][i];
                }
            }
        }
        C -= D[K][(1<<K)-1][N];
        if (C <= 0) {
            printf("%lld\n", T.sum);
            return 0;
        }

        for (int i=1; i<=K; i++){
            Data c = T;
            c.v[i]++;
            if (c.v[i] == (int)comp[i].size()) continue;
            c.sum += comp[i][c.v[i]] - comp[i][c.v[i]-1];
            bool tf = false;
            for (int j=1; j<=K; j++){
                if (R[i][j][c.v[i]] < c.v[j]){
                    tf = true;
                    break;
                }
            }
            if (tf) continue;
            if (vis.find(c) != vis.end()) continue;
            vis.insert(c);
            PQ.push(c);
        }
    }
    return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld", &N, &K, &C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[j][i]);
         ~~~~~^~~~~~~~~~~~~~~~

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