제출 #1189925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189925		crafticat	Kitchen (BOI19_kitchen)	C++20	0 / 100	211 ms	327680 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (int i = 0; i < n;i++)
#define FOR(i, j, n) for(int i = j; i < n;i++)

template<typename T>
using V = vector<T>;
using vi = V<int>;

constexpr int INF = 1e9;

int main() {
    int n, m, k; cin >> n >> m >> k;

    vi a(n), b(m);
    int sumB = 0, sumA = 0;

    F0R(i, n)
        cin >> a[i];
    F0R(i, m)
        cin >> b[i];
    swap(a, b);
    swap(m, n);

    for (auto x : b)
        sumB += x;
    for (auto x : a)
        sumA += x;

    F0R(i, m) {
        if (b[i] < k) {
            cout << "Impossible";
            return 0;
        }
    }

    int BOUND = max(sumB, sumA) + 1;
    V<V<vi>> dp(n + 1, V<vi>(BOUND,vi(k + 1,-INF)));

    dp[0][0][0] = 0;
    FOR(i, 1, n + 1) {
        dp[i][0][0] = 0;
        FOR(j, 1, BOUND) {
            FOR(t, 0, k + 1) {
                if (j - a[i - 1] < 0) continue;
                int oldSum = j - a[i - 1];
                if (t > 0 && dp[i - 1][oldSum][t - 1] + a[i - 1] >= m)
                    dp[i][j][t] = max(dp[i][j][t], 0);
                dp[i][j][t] = max(dp[i][j][t], dp[i - 1][oldSum][t] + a[i - 1]);
            }
        }
    }

    FOR(i, sumB, BOUND) {
        if (dp[n][i][k] >= 0) {
            cout << i - sumB << endl;
            return 0;
        }
    }

    cout << "Impossible";
}

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