Submission #1324113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324113		edo	Kitchen (BOI19_kitchen)	C++20	100 / 100	25 ms	1128 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void die() {
    cout << "Impossible\n";
    exit(0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    
    if(m < k) 
        die();

    vector<int> A(n), B(m);
    int total = 0;
    for(int& i : A) {
        cin >> i;
        if(i < k) 
            die();
        total += i;
    }
    for(int& i : B) cin >> i;

    const int nax = 300 * 300 + 5;
    ll dp[nax];
    memset(dp, -1, sizeof(dp));
    
    dp[0] = 0;
    for(int i = 0; i < m; i++) {
        for(int j = nax - B[i]; ~j; --j) {
            if(dp[j] != -1) {
                dp[j + B[i]] = max(dp[j + B[i]], dp[j] + min(n, B[i]));
            }
        }
    }

    int N = n * k;
    for(int i = total; i < nax; i++) {
        if(dp[i] >= N) {
            cout << i - total;
            return 0;
        }
    }
    die();
    return 0;
}

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