oj.uz

Submission #124911

# Submission time Handle Problem Language Result Execution time Memory
124911 2019-07-04T06:35:29 Z 박상수(#3055) Olympiads (BOI19_olympiads) C++14
100 / 100
 7 ms 1272 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, K, C;
int A[510][10];
ll Bind(int p[], int rk = K) {
    ll res = 0;
    for(int i=1;i<=rk;i++) res = (res << 10 | p[i]);
    return res;
}
void Unbind(ll x, int p[]) {
    for(int i=K;i;i--) p[i] = (x & 1023), x >>= 10;
}

ll CR[2020][10];
int ord[10][510];
ll calc(int temp[]) {
    ll ans = 0;
    for(int a=1;a<=K;a++) ans += A[ord[a][temp[a]]][a];
    return ans;
}

int main() {
    rep(i, 2020) {
        CR[i][0] = 1;
        for(int j=1;j<=i && j<10;j++) {
            CR[i][j] = CR[i-1][j-1] + CR[i-1][j];
        }
    }
    scanf("%d%d%d", &N, &K, &C);
    for(int i=1;i<=N;i++) for(int j=1;j<=K;j++) scanf("%d", A[i] + j);
    for(int i=1;i<=K;i++) {
        for(int j=1;j<=N;j++) ord[i][j] = j;
        sort(ord[i]+1, ord[i]+1+N, [&](int x, int y) { return A[x][i] > A[y][i]; });
    }
    int temp[10];
    for(int i=1;i<=K;i++) temp[i] = 1;
    ll ST = Bind(temp);
    priority_queue <pll> pq;
    pq.push(pll(calc(temp), ST));
    set <ll> Sx2; Sx2.insert(ST);
    while(!pq.empty()) {
        pll tt = pq.top(); pq.pop();
        ll me = tt.Se;
        int t[10];
        Unbind(me, t);
        int rt[10], tp = 0;
        for(int a=1;a<=K;a++) rt[tp++] = ord[a][t[a]];
        sort(rt, rt+tp); tp = (int)(unique(rt, rt+tp) - rt);
        bitset <520> tv; tv.reset();
        for(int a=1;a<=K;a++) for(int b=1;b<t[a];b++) tv[ord[a][b]] = 1;
        vector <int> w;
        for(int a=1;a<=K;a++) if(tv[ord[a][t[a]]]) w.pb(a);
        int cn = N - tv.count();
        if(cn < K) continue;
        if(szz(w) == 0) {
            ll cnt = CR[cn - tp][K - tp];
            if (cnt >= C) {
                printf("%lld\n", tt.Fi);
                break;
            }
            C -= cnt;
        }
        auto upd = [&]() {
            ll v = Bind(t);
            if(Sx2.find(v) == Sx2.end()) {
                Sx2.insert(v);
                pq.push(pll(calc(t), v));
            }
        };
        if(szz(w)) {
            for(int e : w) while(t[e] <= N && tv[ord[e][t[e]]] == 1) t[e]++;
            int can = 1;
            for(int a=1;a<=K;a++) if(t[a] > N) can = 0;
            if(can) upd();
        }
        else {
            for(int a=1;a<=K;a++) if(t[a] != N) {
                ++t[a];
                upd();
                --t[a];
            }
        }
    }
    return 0;
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &K, &C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:59:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=N;i++) for(int j=1;j<=K;j++) scanf("%d", A[i] + j);
                                                 ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 5 ms 888 KB Output is correct
4 Correct 5 ms 888 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 6 ms 1144 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 636 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 5 ms 888 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 6 ms 1144 KB Output is correct
12 Correct 7 ms 1272 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 3 ms 636 KB Output is correct
15 Correct 6 ms 888 KB Output is correct
16 Correct 4 ms 764 KB Output is correct
17 Correct 7 ms 1272 KB Output is correct
18 Correct 7 ms 1144 KB Output is correct
19 Correct 3 ms 504 KB Output is correct