oj.uz

Submission #146940

# Submission time Handle Problem Language Result Execution time Memory
146940 2019-08-26T17:35:17 Z Vlatko Olympiads (BOI19_olympiads) C++14
100 / 100
 69 ms 1116 KB 
#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 500;
const int maxk = 6;

int n, k, c;
int p[maxn][maxk];

struct State {
    int score, start;
    int best[maxk]; // indices of people in team
    bitset<maxn> forbidden; // indices already used

    State() {
        start = 0;
        calc_score();
    }
    State(State* pre, int new_start) {
        start = new_start;
        forbidden = pre->forbidden;
        forbidden[pre->best[start]] = true;
        for (int i = 0; i < start; ++i) {
            best[i] = pre->best[i];
        }
        calc_score();
    }
    void calc_score() {
        for (int j = start; j < k; ++j) {
            int besti = -1;
            for (int i = 0; i < n; ++i) {
                if (forbidden[i] || in_best(j, i)) {
                    continue;
                }
                if (besti == -1 || p[i][j] > p[besti][j]) {
                    besti = i;
                }
            }
            if (besti == -1) {
                score = -1e9;
                return;
            }
            best[j] = besti;
        }
        score = 0;
        for (int j = 0; j < k; ++j) {
            int res = 0;
            for (int i = 0; i < k; ++i) {
                res = max(res, p[best[i]][j]);
            }
            score += res;
        }
    }
    bool in_best(int end, int x) {
        for (int i = 0; i < end; ++i) {
            if (best[i] == x) {
                return true;
            }
        }
        return false;
    }
};

struct State_Compare {
    bool operator () (State* l, State* r) {
        return l->score < r->score;
    }
};

priority_queue<State*, vector<State*>, State_Compare> pq;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> c;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            cin >> p[i][j];
        }
    }
    int ans = 0;
    pq.push(new State());
    State* top;
    while (c--) {
        top = pq.top();
        pq.pop();
        ans = top->score;
        for (int i = top->start; i < k; ++i) {
            pq.push(new State(top, i));
        }
    }
    cout << ans << endl;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 6 ms 504 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 6 ms 888 KB Output is correct
4 Correct 5 ms 760 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct
3 Correct 38 ms 988 KB Output is correct
4 Correct 40 ms 952 KB Output is correct
5 Correct 14 ms 632 KB Output is correct
6 Correct 5 ms 760 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 6 ms 888 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 9 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 38 ms 988 KB Output is correct
12 Correct 40 ms 952 KB Output is correct
13 Correct 14 ms 632 KB Output is correct
14 Correct 5 ms 760 KB Output is correct
15 Correct 14 ms 632 KB Output is correct
16 Correct 24 ms 760 KB Output is correct
17 Correct 69 ms 1116 KB Output is correct
18 Correct 27 ms 888 KB Output is correct
19 Correct 7 ms 504 KB Output is correct