Submission #984343

#	Time	Username	Problem	Language	Result	Execution time	Memory
984343		kh0i	Olympiads (BOI19_olympiads)	C++17	100 / 100	27 ms	7352 KiB

olympiads

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, k, c;
vector<vector<int>> a;

struct Partition{
    vector<int> span;
    int fix = 0;
    ll weight = 0;

    Partition(vector<int> _span, int _fix) : span(_span), fix(_fix){
        for(int j = 0; j < k; ++j){
            int mx = 0;
            for(int i = 0; i < k; ++i)
                mx = max(mx, a[span[i]][j]);
            weight += mx;
        }
    }

    bool friend operator < (const Partition &x, const Partition &y){ return x.weight < y.weight; }
};

void sort(vector<int> &x){
    for(int i = 0; i < k; ++i)
        for(int j = i + 1; j < sz(x); ++j)
            if(a[x[i]][i] < a[x[j]][i])
                swap(x[i], x[j]);
}

void solve(){
    cin >> n >> k >> c;
    a.resize(n, vector<int>(k, 0));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < k; ++j)
           cin >> a[i][j];
    
    vector<int> cur(n);
    iota(all(cur), 0);

    sort(cur);

    priority_queue<Partition> pq;
    pq.push(Partition(cur, 0));

    for(int iter = 1; iter <= c; ++iter){
        assert(!pq.empty());
        Partition a = pq.top();
        pq.pop();

        debug(a.weight, a.span);

        if(iter == c){
            cout << a.weight;
            return;
        }

        if(sz(a.span) == k)
            continue;

        while(a.fix < k){
            vector<int> tmp = a.span;
            tmp.erase(tmp.begin() + a.fix);
            sort(tmp);
            pq.push(Partition(tmp, a.fix));
            ++a.fix;
        }
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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