Submission #240319

#	Time	Username	Problem	Language	Result	Execution time	Memory
240319		karma	Olympiads (BOI19_olympiads)	C++14	100 / 100	28 ms	1660 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], value[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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;
unordered_map<int, bool> vis;
int cost[K][K], mask, ncost, val, has[N];
vector<pii> maxv[K];

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) {
        value[i] = uniform_int_distribution<int>(10000000, 100000000)(rng);
        for(int j = 0; j < k; ++j) {
            cin >> s[i][j];
            maxv[j].pb(s[i][j], i);
        }
    }
    for(int j = 0; j < k; ++j) {
        s[0][j] = -1;
        sort(maxv[j].begin(), maxv[j].end(), greater<pii>());
    }
    vector<int> tmp; ncost = mask = 0;
    for(int mx, j = 0; j < k; ++j) {
        mx = 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) {
        mask ^= value[x];
        has[x] = 0;
    }
    vis[mask] = 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;
        mask = 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;
            mask ^= value[top.id[x]];
        }
        bool ok;
        for(int i = 0; i < k; ++i) {
            ok = 0;
            for(auto x: maxv[i]) {
                if(has[x.se]) continue;
                val = top.id[i]; /// change j
                mask ^= value[val] ^ value[x.se];
                if(!vis[mask]) {
                    vis[mask] = 1; ncost = 0; top.id[i] = x.se;
                    for(int j = 0; j < k; ++j) ncost += max(cost[i][j], s[x.se][j]);
                    pq.emplace(top.id, ncost); top.id[i] = val;
                    ok = 1;
                }
                mask ^= value[val] ^ value[x.se];
                if(ok) break;
            }
        }
        for(int x: top.id) has[x] = 0;
    }
}

Compilation message (stderr)

olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:36: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:37: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: 24 / 24
• Subtask 4: 32 / 32