# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
850776 | serifefedartar | Olympiads (BOI19_olympiads) | C++17 | 135 ms | 20448 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 505;
vector<vector<int>> p;
int N, K, C;
struct Rule {
vector<int> r;
int res;
Rule(vector<int> rl) {
r = rl;
res = 0;
}
int calc() {
int cnt = 0;
for (int i = 0; i < r.size(); i++) {
if (r[i] == 2)
r[i] = 0;
}
set<int> taken;
for (int i = 0; i < N; i++) {
if (r[i] == 1) {
cnt++;
taken.insert(i);
}
}
for (int i = cnt; i < K; i++) {
int mx = 0;
int mx_ind = -1;
for (int j = 0; j < N; j++) {
if (r[j] != -1 && taken.count(j) == 0 && mx <= p[j][i]) {
mx = p[j][i];
mx_ind = j;
}
}
if (mx_ind != -1)
taken.insert(mx_ind);
}
if (taken.size() != K)
res = -1;
else {
for (auto u : taken)
r[u] = 2;
for (int i = 0; i < K; i++) {
int mx_here = 0;
for (auto u : taken)
mx_here = max(mx_here, p[u][i]);
res += mx_here;
}
}
return res;
}
};
bool operator <(Rule A, Rule B) {
return A.res < B.res;
}
int main() {
fast
cin >> N >> K >> C;
p = vector<vector<int>>(N, vector<int>(K));
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++)
cin >> p[i][j];
}
priority_queue<Rule> pq;
vector<int> emp(N, 0);
Rule new_rule = Rule(emp);
new_rule.calc();
pq.push(new_rule);
while (true) {
Rule now = pq.top();
pq.pop();
C--;
if (C == 0) {
cout << now.res << "\n";
exit(0);
}
vector<int> R = now.r;
for (int i = 0; i < N; i++) {
if (R[i] == 2) {
R[i] = -1;
new_rule = Rule(R);
new_rule.calc();
pq.push(new_rule);
R[i] = 1;
}
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |