Submission #296469

#	Time	Username	Problem	Language	Result	Execution time	Memory
296469		alexandra_udristoiu	Olympiads (BOI19_olympiads)	C++14	100 / 100	38 ms	3064 KiB

olympiads

#include<iostream>
#include<cstring>
using namespace std;
int n, k, i, j, nr, c, x;
int a[505][7], curr[505];
struct str{
    int scor, sol[7];
    char f[505];
};
str h[12005];
void calc(str &x){
    int i, ind, j, maxim;
    memset(curr, 0, sizeof(curr) );
    for(i = 1; i <= k; i++){
        ind = x.sol[i];
        if(x.f[ind] != 2){
            break;
        }
    }
    for(; i <= k; i++){
        maxim = -1;
        ind = -1;
        for(j = 1; j <= n; j++){
            if(x.f[j] == 0 && curr[j] == 0 && a[j][i] > maxim){
                maxim = a[j][i];
                ind = j;
            }
        }
        if(ind == -1){
            x.scor = -1000000000;
            return;
        }
        curr[ind] = 1;
        x.sol[i] = ind;
    }
    x.scor = 0;
    for(i = 1; i <= k; i++){
        maxim = 0;
        for(j = 1; j <= k; j++){
            maxim = max(maxim, a[ x.sol[j] ][i]);
        }
        x.scor += maxim;
    }
}
void upd(int c){
    int p = c / 2;
    while(p > 0 && h[p].scor < h[c].scor){
        swap(h[p], h[c]);
        c = p;
        p = c / 2;
    }
}
void elim(){
    int p = 1, c = 2;
    while(c <= nr){
        if(c + 1 <= nr && h[c + 1].scor > h[c].scor){
            c++;
        }
        if(h[c].scor > h[p].scor){
            swap(h[p], h[c]);
            p = c;
            c = 2 * p;
        }
        else{
            break;
        }
    }
}
int main(){
    cin>> n >> k >> c;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= k; j++){
            cin>> a[i][j];
        }
    }
    nr = 1;
    calc(h[1]);
    for(; c > 1; c--){
        for(j = 1; j <= k; j++){
            if(h[1].f[ h[1].sol[j] ] != 2){
                break;
            }
        }
        for(; j <= k; j++){
            x = h[1].sol[j];
            h[1].f[x] = 1;
            h[++nr] = h[1];
            calc(h[nr]);
            upd(nr);
            h[1].f[x] = 2;
        }
        swap(h[1], h[nr]);
        nr--;
        elim();
    }
    cout<< h[1].scor;
}

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