Submission #462477

#	Time	Username	Problem	Language	Result	Execution time	Memory
462477		Ozy	Olympiads (BOI19_olympiads)	C++17	100 / 100	46 ms	33396 KiB

olympiads

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define num first
#define id second

struct x {
    lli forbiden[502];
    lli act[8];
    lli ini;
    lli val;

    bool operator < (const x &a)
    const {
        return val < a.val;
    }
};

priority_queue<x> cola;
lli n,c,k,a,cont;
lli arr[502][8],MAX[8];
vector<pair<lli,lli> > orden[8];
x p,nuevo;

lli suma(x &pp) {

    rep(i,1,k) MAX[i] = 0;

    rep(i,1,k) {
        rep(j,1,k) {
            MAX[j] = max(MAX[j],  arr[ orden[i][pp.act[i]].id ][j]  );
        }
    }

    lli s = 0;
    rep(i,1,k) s += MAX[i];
    return s;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k >> c;
    rep(i,1,n) {
        rep(j,1,k) {
            cin >> arr[i][j];
            orden[j].push_back({arr[i][j], i});
        }
    }
    rep(i,1,k) {
        sort(orden[i].begin(),orden[i].end());
        reverse(orden[i].begin(), orden[i].end());

        p.act[i] = 0;
        while (p.act[i] < n && p.forbiden[ orden[i][p.act[i]].id ] == 1) p.act[i]++;

        p.forbiden[ orden[i][p.act[i]].id ] = 1;
    }

    p.val = suma(p);
    p.ini = 1;
    cola.push(p);
    cont = 1;

    while (!cola.empty()) {

        p = cola.top();
        cola.pop();

        if (cont == c) {cout << p.val; return 0;}
        cont++;

        rep(t,p.ini,k) {

            nuevo = p;
            nuevo.ini = t;
            while (nuevo.act[t] < n && nuevo.forbiden[ orden[t][nuevo.act[t]].id ] == 1) nuevo.act[t]++;

            if (nuevo.act[t] == n) continue;

            nuevo.forbiden[ orden[t][nuevo.act[t]].id ] = 1;

            nuevo.val = suma(nuevo);
            cola.push(nuevo);
        }

    }

}

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