oj.uz

Submission #984343

# Submission time Handle Problem Language Result Execution time Memory
984343 2024-05-16T14:10:47 Z kh0i Olympiads (BOI19_olympiads) C++17
100 / 100
 27 ms 7352 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 5 ms 572 KB Output is correct
3 Correct 4 ms 524 KB Output is correct
4 Correct 3 ms 604 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 2 ms 600 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Output is correct
2 Correct 6 ms 604 KB Output is correct
3 Correct 25 ms 6240 KB Output is correct
4 Correct 22 ms 5720 KB Output is correct
5 Correct 9 ms 1372 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 5 ms 572 KB Output is correct
3 Correct 4 ms 524 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 10 ms 600 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 25 ms 6240 KB Output is correct
12 Correct 22 ms 5720 KB Output is correct
13 Correct 9 ms 1372 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 14 ms 1628 KB Output is correct
16 Correct 18 ms 4644 KB Output is correct
17 Correct 27 ms 7352 KB Output is correct
18 Correct 21 ms 4184 KB Output is correct
19 Correct 6 ms 604 KB Output is correct