Submission #745868

#	Time	Username	Problem	Language	Result	Execution time	Memory
745868		vjudge1	Kitchen (BOI19_kitchen)	C++17	100 / 100	26 ms	596 KiB

kitchen

#include <iostream>
#include <vector>

using namespace std;

int const MAX_N = 300;
int const MAX_M = 300;
int const MAX_WORK = MAX_N * (MAX_M + 1);

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

    vector<int> dp(MAX_WORK + 1, -1);

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n);
    int total_work = 0;

    for (int& x : a) {
        cin >> x;

        total_work += x;

        if (x < k) {
            cout << "Impossible\n";
            return 0;
        }
    }

    int const difference_work = n * k;

    if (total_work > MAX_WORK || difference_work > MAX_WORK) {
        cout << "Impossible\n";
        return 0;
    }

    vector<int> b(m);
    for (int& x : b)
        cin >> x;
    
    dp[0] = 0;

    for (int const& chef : b) {
        int const delta_d = min(chef, n);
        int const delta_t = chef;

        for (int t = MAX_WORK; t >= delta_t; t--) {
            if (dp[t - delta_t] == -1)
                continue;

            int const new_d = dp[t - delta_t] + delta_d;

            dp[t] = max(dp[t], new_d);
        }
    }

    for (int t = total_work; t <= MAX_WORK; t++) {
        if (dp[t] >= difference_work) {
            cout << t - total_work << "\n";
            return 0;
        }
    }

    cout << "Impossible\n";
}

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