oj.uz

Submission #567020

# Submission time Handle Problem Language Result Execution time Memory
567020 2022-05-23T07:20:23 Z shrimb Kitchen (BOI19_kitchen) C++17
51 / 100
 174 ms 107108 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[40][40*40][40*40];
map<array<int,3>, int> dp4;

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];
    if (dp4.count({i, sm, sm2})) 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)));
    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 (max({n, m, k, *max_element(A, A+n), *max_element(B,B+m)}) <= 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 75 ms 107104 KB Output is correct
2 Correct 74 ms 107108 KB Output is correct
3 Correct 130 ms 107060 KB Output is correct
4 Correct 174 ms 106968 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 68 ms 107064 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 4736 KB Output isn't correct
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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 75 ms 107104 KB Output is correct
15 Correct 74 ms 107108 KB Output is correct
16 Correct 130 ms 107060 KB Output is correct
17 Correct 174 ms 106968 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 68 ms 107064 KB Output is correct
20 Incorrect 46 ms 4736 KB Output isn't correct
21 Halted 0 ms 0 KB -