Submission #240314

#	Time	Username	Problem	Language	Result	Execution time	Memory
240314		karma	Olympiads (BOI19_olympiads)	C++14	44 / 100	2094 ms	257772 KiB

olympiads

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = int(5e2) + 7;
const int K = 7;
typedef pair<int, int> pii;

int n, k, c, s[N][K];
struct Team {
    vector<int> id;
    int cost;
    Team() {};
    Team(vector<int> id, int cost): id(id), cost(cost) {}
    bool operator <(const Team& other) const& {
        return cost < other.cost;
    }
};
priority_queue<Team> pq;
map<vector<int>, bool> vis;
int cost[K][K], has[N];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> k >> c;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < k; ++j) cin >> s[i][j];
    }
    for(int j = 0; j < k; ++j) s[0][j] = -1;
    vector<int> tmp; int ncost = 0, val;
    for(int mx, j = 0; j < k; ++j) {
        mx = 0; val = 0;
        for(int i = 1; i <= n; ++i) {
            if(has[i]) {val = max(val, s[i][j]); continue;}
            if(s[mx][j] < s[i][j]) mx = i;
        }
        tmp.pb(mx); ncost += max(val, s[mx][j]), has[mx] = 1;
    }
    for(int x: tmp) has[x] = 0; sort(tmp.begin(), tmp.end());
    vis[tmp] = 1;
    pq.emplace(tmp, ncost);
    for(Team top; pq.size() && c > 0;) {
        top = pq.top(); pq.pop();
        if(--c == 0) return cout << top.cost, 0;
        for(int x = 0; x < k; ++x) { /// cost[x][i] neu bo id[x]
            for(int i = 0; i < k; ++i) {
                cost[x][i] = 0;
                for(int j = 0; j < k; ++j)
                    if(j != x) cost[x][i] = max(cost[x][i], s[top.id[j]][i]);
            }
            has[top.id[x]] = 1;
        }
        for(int ncost, i = 1; i <= n; ++i) {
            if(has[i]) {has[i] = 0; continue;}
            for(int j = 0; j < k; ++j) {
                ncost = 0; tmp = top.id, tmp[j] = i; /// change j
                sort(tmp.begin(), tmp.end());
                if(vis[tmp]) continue;
                vis[tmp] = 1;
                for(int x = 0; x < k; ++x) ncost += max(cost[j][x], s[i][x]);
                pq.emplace(tmp, ncost);
            }
        }
    }
}

Compilation message (stderr)

olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:51:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int x: tmp) has[x] = 0; sort(tmp.begin(), tmp.end());
     ^~~
olympiads.cpp:51:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int x: tmp) has[x] = 0; sort(tmp.begin(), tmp.end());
                                 ^~~~
olympiads.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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