oj.uz

Submission #229206

# Submission time Handle Problem Language Result Execution time Memory
229206 2020-05-03T18:23:41 Z dolphingarlic Olympiads (BOI19_olympiads) C++14
100 / 100
 112 ms 1716 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Frag {
    int score;
    vector<int> best, forced;
    vector<bool> forbidden;
};

bool operator<(Frag A, Frag B) { return A.score < B.score; }

int n, k, c, stud[500][6];

Frag fill_best(Frag init) {
    init.best = init.forced;
    init.score = 0;
    FOR(i, init.best.size(), k) {
        init.best.push_back(-1);
        FOR(j, 0, n)
            if (!init.forbidden[j] && find(init.best.begin(), init.best.end(), j) == init.best.end())
                if (init.best[i] == -1 || stud[init.best[i]][i] < stud[j][i])
                    init.best.pop_back(), init.best.push_back(j);
    }
    vector<int> event_best(k, 0);
    FOR(i, 0, k) if (~init.best[i]) FOR(j, 0, k) event_best[j] = max(event_best[j], stud[init.best[i]][j]);
    FOR(i, 0, k) init.score += event_best[i];
    return init;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> c;
    FOR(i, 0, n) FOR(j, 0, k) cin >> stud[i][j];
    priority_queue<Frag> pq;
    pq.push(fill_best({0, {}, {}, vector<bool>(n, false)}));
    while (c--) {
        Frag curr = pq.top();
        pq.pop();

        if (!c) cout << curr.score;
        FOR(i, curr.forced.size(), k) {
            curr.forbidden[curr.best[i]] = true;
            Frag nxt = fill_best(curr);
            if (find(nxt.best.begin(), nxt.best.end(), -1) == nxt.best.end())
                pq.push(nxt);
            curr.forbidden[curr.best[i]] = false;
            curr.forced.push_back(curr.best[i]);
        }
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 21 ms 384 KB Output is correct
4 Correct 16 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 640 KB Output is correct
2 Correct 20 ms 384 KB Output is correct
3 Correct 30 ms 1016 KB Output is correct
4 Correct 26 ms 744 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 384 KB Output is correct
2 Correct 18 ms 384 KB Output is correct
3 Correct 73 ms 1204 KB Output is correct
4 Correct 77 ms 1076 KB Output is correct
5 Correct 40 ms 640 KB Output is correct
6 Correct 23 ms 640 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 21 ms 384 KB Output is correct
4 Correct 16 ms 384 KB Output is correct
5 Correct 26 ms 640 KB Output is correct
6 Correct 20 ms 384 KB Output is correct
7 Correct 30 ms 1016 KB Output is correct
8 Correct 26 ms 744 KB Output is correct
9 Correct 23 ms 384 KB Output is correct
10 Correct 18 ms 384 KB Output is correct
11 Correct 73 ms 1204 KB Output is correct
12 Correct 77 ms 1076 KB Output is correct
13 Correct 40 ms 640 KB Output is correct
14 Correct 23 ms 640 KB Output is correct
15 Correct 33 ms 512 KB Output is correct
16 Correct 60 ms 1016 KB Output is correct
17 Correct 112 ms 1716 KB Output is correct
18 Correct 55 ms 888 KB Output is correct
19 Correct 20 ms 384 KB Output is correct