oj.uz

Submission #698465

# Submission time Handle Problem Language Result Execution time Memory
698465 2023-02-13T14:26:32 Z jiahng Olympiads (BOI19_olympiads) C++14
100 / 100
 299 ms 26108 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define int ll
typedef pair<int, int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair <pi,pi> pipi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 510
#define INF (ll)1e18
#define MOD 998244353
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0
#pragma GCC optimize("trapv")

int N,K,C,A[maxn][10];

vector <vi> enc, gua,b;
vi val;
int tmp[10];

int32_t main(){
    cin >> N >> K >> C;
    FOR(i,1,N) FOR(j,1,K) cin >> A[i][j];
    
    enc.pb(vi()); gua.pb(vi());
    FOR(i,1,N) enc[0].pb(i);
    
    b.pb(vi());
    FOR(i,1,K){
        pi mx = pi(0,0);
        aFOR(j, enc[0]){
            bool used = 0;
            aFOR(k, b[0]) if (j == k) used = 1;
            if (!used) mx = max(mx, pi(A[j][i], j));
        }
        b[0].pb(mx.s);
    }
    aFOR(i, b[0]){
        FOR(j,1,K) tmp[j] = max(tmp[j], A[i][j]);
    }
    val.pb(0);
    FOR(j,1,K) val[0] += tmp[j];
    
    priority_queue <pi> pq;
    pq.push(pi(val[0], 0));

    FOR(_,1,C-1){
        pi cur = pq.top(); pq.pop();
        if (DEBUG){
            cout << cur.f << '\n';
            cout << "gua: ";
            aFOR(i, gua[cur.s]) cout << i << ' ';
            cout << '\n';
            cout << "enc: ";
            aFOR(i, enc[cur.s]) cout << i << ' ';
            cout << '\n';
            cout << "b: ";
            aFOR(i, b[cur.s]) cout << i << ' ';
            cout << '\n';
        }

        if (enc[cur.s].size() + gua[cur.s].size() == K) continue;
        FOR(i,gua[cur.s].size()+1,K){
            // guarantee b[cur.s][0...i-2], exclude b[cur.s][i-1]

            enc.pb(vi()); gua.pb(vi());
            FOR(j,0,i-2) gua.back().pb(b[cur.s][j]);
            aFOR(j, enc[cur.s]){
                bool rm = 0;
                FOR(k,0,i-1) if (j == b[cur.s][k]) rm = 1;
                if (!rm) enc.back().pb(j);
            }
                
            b.pb(vi());
            aFOR(x, gua.back()) b.back().pb(x);

            FOR(j,gua.back().size()+1,K){
                pi mx = pi(0,0);
                aFOR(x, enc.back()){
                    bool used = 0;
                    aFOR(y, b.back()) if (x == y) used = 1;
                    if (!used) mx = max(mx, pi(A[x][j], x));
                }
                b.back().pb(mx.s);
            }
            FOR(j,1,K) tmp[j] = 0;
            aFOR(j, b.back()){
                FOR(k,1,K) tmp[k] = max(tmp[k], A[j][k]);
            }
            val.pb(0);
            FOR(j,1,K) val.back() += tmp[j];

            pq.push(pi(val.back(), val.size()-1));
        }
    } 
    cout << pq.top().f;
}

Compilation message

olympiads.cpp: In function 'int32_t main()':
olympiads.cpp:81:51: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   81 |         if (enc[cur.s].size() + gua[cur.s].size() == K) continue;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7172 KB Output is correct
2 Correct 38 ms 8232 KB Output is correct
3 Correct 34 ms 7424 KB Output is correct
4 Correct 25 ms 5940 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1748 KB Output is correct
2 Correct 6 ms 1200 KB Output is correct
3 Correct 17 ms 2388 KB Output is correct
4 Correct 13 ms 1916 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7376 KB Output is correct
2 Correct 44 ms 6044 KB Output is correct
3 Correct 267 ms 22320 KB Output is correct
4 Correct 243 ms 21492 KB Output is correct
5 Correct 188 ms 17740 KB Output is correct
6 Correct 7 ms 1388 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7172 KB Output is correct
2 Correct 38 ms 8232 KB Output is correct
3 Correct 34 ms 7424 KB Output is correct
4 Correct 25 ms 5940 KB Output is correct
5 Correct 10 ms 1748 KB Output is correct
6 Correct 6 ms 1200 KB Output is correct
7 Correct 17 ms 2388 KB Output is correct
8 Correct 13 ms 1916 KB Output is correct
9 Correct 59 ms 7376 KB Output is correct
10 Correct 44 ms 6044 KB Output is correct
11 Correct 267 ms 22320 KB Output is correct
12 Correct 243 ms 21492 KB Output is correct
13 Correct 188 ms 17740 KB Output is correct
14 Correct 7 ms 1388 KB Output is correct
15 Correct 118 ms 11524 KB Output is correct
16 Correct 181 ms 16352 KB Output is correct
17 Correct 299 ms 26108 KB Output is correct
18 Correct 199 ms 17444 KB Output is correct
19 Correct 43 ms 6164 KB Output is correct