oj.uz

Submission #462477

# Submission time Handle Problem Language Result Execution time Memory
462477 2021-08-10T16:01:25 Z Ozy Olympiads (BOI19_olympiads) C++17
100 / 100
 46 ms 33396 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 7 ms 716 KB Output is correct
4 Correct 5 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8692 KB Output is correct
2 Correct 32 ms 16892 KB Output is correct
3 Correct 27 ms 16932 KB Output is correct
4 Correct 20 ms 8624 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 968 KB Output is correct
2 Correct 6 ms 588 KB Output is correct
3 Correct 29 ms 16928 KB Output is correct
4 Correct 30 ms 16936 KB Output is correct
5 Correct 43 ms 33396 KB Output is correct
6 Correct 27 ms 16812 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 716 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 7 ms 716 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 19 ms 8692 KB Output is correct
6 Correct 32 ms 16892 KB Output is correct
7 Correct 27 ms 16932 KB Output is correct
8 Correct 20 ms 8624 KB Output is correct
9 Correct 7 ms 968 KB Output is correct
10 Correct 6 ms 588 KB Output is correct
11 Correct 29 ms 16928 KB Output is correct
12 Correct 30 ms 16936 KB Output is correct
13 Correct 43 ms 33396 KB Output is correct
14 Correct 27 ms 16812 KB Output is correct
15 Correct 14 ms 4644 KB Output is correct
16 Correct 34 ms 16936 KB Output is correct
17 Correct 46 ms 33396 KB Output is correct
18 Correct 21 ms 8760 KB Output is correct
19 Correct 6 ms 588 KB Output is correct