Submission #1096070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096070		MateiKing80	Olympiads (BOI19_olympiads)	C++14	100 / 100	19 ms	3120 KiB

olympiads

#include<bits/stdc++.h>

using namespace std;

int n, k, i, j, nr, c, x;
int a[505][7], curr[505];

struct ura
{
    int scor, sol[7];
    char f[505];
};
ura h[12005];

void calc(ura &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