제출 #1224220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224220		thinknoexit	Kitchen (BOI19_kitchen)	C++20	100 / 100	14 ms	1232 KiB

kitchen

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 303;
const int K = 90000;
int a[N];
bitset<N* N> dp1;
int dp2[N * N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(dp2, 0xc0, sizeof dp2);
    int n, m, k;
    cin >> n >> m >> k;
    int sum = 0;
    for (int i = 1;i <= n;i++) cin >> a[i], sum += a[i];
    for (int i = 1;i <= n;i++) {
        if (a[i] < k) {
            cout << "Impossible\n";
            return 0;
        }
    }
    dp1[0] = 1;
    dp2[0] = 0;
    for (int i = 1;i <= m;i++) {
        int b;
        cin >> b;
        if (b < n) {
            dp1 |= (dp1 << b);
        }
        else {
            for (int j = K;j >= b;j--) dp2[j] = max(dp2[j], dp2[j - b] + 1);
        }
    }
    vector<int> can;
    for (int i = 0;i <= K;i++) {
        if (dp1[i]) can.push_back(i);
    }
    int mn = 1e9;
    for (int i = 0;i <= K;i++) {
        if (dp2[i] < 0) continue;
        int need = max(sum - i, (k - dp2[i]) * n);
        if (can.back() < need) continue;
        mn = min(mn, *lower_bound(can.begin(), can.end(), need) + i);
    }
    if (mn == 1e9) cout << "Impossible\n";
    else cout << mn - sum << '\n';
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28