Submission #698465

#	Time	Username	Problem	Language	Result	Execution time	Memory
698465		jiahng	Olympiads (BOI19_olympiads)	C++14	100 / 100	299 ms	26108 KiB

olympiads

#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 (stderr)

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 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32