oj.uz

Submission #587014

# Submission time Handle Problem Language Result Execution time Memory
587014 2022-07-01T08:10:41 Z 박상훈(#8395) Olympiads (BOI19_olympiads) C++17
100 / 100
 18 ms 760 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct State{
    vector<int> v;
    int ans, s, ok;
    State(){}
    State(vector<int> _v, int _ans, int _s, int _ok): v(_v), ans(_ans), s(_s), ok(_ok) {}
    bool operator < (const State &S) const{
        return ans < S.ans;
    }
};

int n, k, C;
pair<int, int> a[505][6], b[6][505];

int ncr(int n, int r){
    assert(r<=6);
    ll ret = 1;
    for (int i=n;i>=n-r+1;i--) ret *= i;
    for (int i=1;i<=r;i++) ret /= i;
    return min(ret, (ll)C+1);
}

int sum(vector<int> v){
    int ret = 0;
    for (int j=0;j<k;j++) ret += b[j][v[j]].first;
    return ret;
}

int _count(vector<int> v){
    vector<int> used;
    for (int j=0;j<k;j++) used.push_back(b[j][v[j]].second);
    sort(used.begin(), used.end());
    used.erase(unique(used.begin(), used.end()), used.end());

    int r = k - used.size();
    int q = 0;
    for (int i=1;i<=n;i++){
        bool flag = 1;
        for (int j=0;j<k;j++) if (a[i][j] >= b[j][v[j]]) flag = 0;
        if (flag) q++;
    }

    return ncr(q, r);
}

bool valid(vector<int> v){
    vector<int> used;
    for (int j=0;j<k;j++) used.push_back(b[j][v[j]].second);
    sort(used.begin(), used.end());
    used.erase(unique(used.begin(), used.end()), used.end());

    for (auto &i:used){
        for (int j=0;j<k;j++) if (a[i][j] > b[j][v[j]]){
            /*printf("Not Valid: ");
            for (auto &x:v) printf("%d ", x);
            printf("/ a[%d][%d] = %d > b[%d][%d] = %d", i, j, a[i][j].first, j, v[j], b[j][v[j]].first);
            printf("\n");*/
            return 0;
        }
    }
    return 1;
}

int main(){
    scanf("%d %d %d", &n, &k, &C);
    for (int i=1;i<=n;i++){
        for (int j=0;j<k;j++){
            scanf("%d", &b[j][i].first);
            b[j][i].second = i;
            a[i][j] = b[j][i];
        }
    }

    for (int j=0;j<k;j++) sort(b[j]+1, b[j]+n+1, greater<pair<int, int>>());

    priority_queue<State> pq;
    pq.emplace(vector<int>(k, 1), sum(vector<int>(k, 1)), 0, 1);
    while(!pq.empty()){
        auto S = pq.top(); pq.pop();
        /*if (S.ok &&valid(S.v)){
            for (auto &x:S.v) printf("%d ", x);
            printf(": %d %d\n", sum(S.v), _count(S.v));
        }*/

        if (S.ok && valid(S.v)) C -= _count(S.v);

        if (C<=0){
            printf("%d\n", S.ans);
            return 0;
        }

        auto nxt = S.v;
        if (nxt[S.s]<n){
            nxt[S.s]++;
            pq.emplace(nxt, sum(nxt), S.s, 1);
        }
        if (S.s+1<k) pq.emplace(S.v, S.ans, S.s+1, 0);

    }

    assert(false);
    return 0;
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d %d %d", &n, &k, &C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             scanf("%d", &b[j][i].first);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 356 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 17 ms 628 KB Output is correct
4 Correct 17 ms 612 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 5 ms 336 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 10 ms 356 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 17 ms 628 KB Output is correct
12 Correct 17 ms 612 KB Output is correct
13 Correct 8 ms 724 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 10 ms 440 KB Output is correct
16 Correct 4 ms 468 KB Output is correct
17 Correct 18 ms 760 KB Output is correct
18 Correct 13 ms 512 KB Output is correct
19 Correct 1 ms 320 KB Output is correct