oj.uz

Submission #566996

# Submission time Handle Problem Language Result Execution time Memory
566996 2022-05-23T07:08:53 Z shrimb Kitchen (BOI19_kitchen) C++17
51 / 100
 159 ms 262144 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

// #define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 301;

int n, m, k, cntAK, cntBN, smA, smB, ans = 1e9;

int A[maxn], B[maxn];

int dp3[maxn][maxn*maxn];
int dp4[41][41*41][41*41];

int rec3 (int i, int sm) {
    if (sm >= smA) return sm - smA;
    if (i == m) return 1e9;
    if (dp3[i][sm] != -1) return dp3[i][sm];
    return dp3[i][sm] = min(rec3(i + 1, sm), rec3(i + 1, sm + B[i]));
}

int rec4 (int i, int sm, int sm2) {
    if (i == m) {
        if (sm >= smA and sm2/n >= k) return sm - smA;
        return 1e9;
    }
    if (dp4[i][sm][sm2] != -1) return dp4[i][sm][sm2];
    return dp4[i][sm][sm2] = max(rec4(i + 1, sm, sm2), rec4(i + 1, sm + B[i], sm2 + min(B[i], n)));
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 0 ; i < n ; i++) {
        cin >> A[i];
        smA += A[i];
        if (A[i] < k) cntAK++;
    }
    for (int i = 0 ; i < m ; i++) {
        cin >> B[i];
        cntBN += min(n, B[i]);
        smB += B[i];
    }
    if (m < k || smB < smA || cntBN/n < k || cntAK) {
        // assert(0);
        cout << "Impossible\n";
        return 0;
    }
    if (m <= 15) { // subtasks 1 and 2
        for (int i = 0 ; i < (1 << m) ; i++) {
            smB = 0, cntBN = 0;
            if (__builtin_popcount(i) < k) continue;
            for (int j = 0 ; j < m ; j++) {
                if (i & (1 << j)) {
                    smB += B[j];
                    cntBN += min(n, B[j]);
                }
            }
            if (smB >= smA and cntBN/n >= k) ans = min(ans, smB - smA);
        }
        cout << ans << endl;
        return 0;
    }
    if (k == 1) {
        memset(dp3, -1, sizeof dp3);
        cout << rec3(0, 0) << endl;
        return 0;
    }
    if (40 <= 40) {
        memset(dp4, -1, sizeof dp4);
        cout << rec4(0,0,0) << endl;
        return 0;
    }
}


/*

impossible:

- M < K
- sum of B < sum of A
- the number of (B >= N) is < K
- theres an A which is < K

*/

Compilation message

kitchen.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 107060 KB Output is correct
2 Correct 61 ms 106964 KB Output is correct
3 Correct 117 ms 107064 KB Output is correct
4 Correct 159 ms 107060 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 64 ms 107056 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 82 ms 107060 KB Output is correct
15 Correct 61 ms 106964 KB Output is correct
16 Correct 117 ms 107064 KB Output is correct
17 Correct 159 ms 107060 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 64 ms 107056 KB Output is correct
20 Runtime error 99 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -