oj.uz

Submission #984331

# Submission time Handle Problem Language Result Execution time Memory
984331 2024-05-16T13:49:46 Z kh0i Olympiads (BOI19_olympiads) C++17
0 / 100
 110 ms 18876 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{
    ll weight = 0;
    vector<int> span;

    Partition(vector<int> _span) : span(_span){
        for(int j = 0; j < k; ++j){
            int mx = 0;
            for(int i = 0; i < sz(span); ++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));

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

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

        if(sz(a.span) == k)
            continue;
        for(int i = 0; i < k; ++i){
            vector<int> tmp = a.span;
            tmp.erase(tmp.begin() + i);
            sort(tmp);
            pq.push(Partition(tmp));
        }
    }
}

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:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 18732 KB Output is correct
2 Correct 84 ms 16776 KB Output is correct
3 Incorrect 110 ms 18876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4188 KB Output isn't correct
2 Halted 0 ms 0 KB -