Submission #1189954

#TimeUsernameProblemLanguageResultExecution timeMemory
1189954crafticatKitchen (BOI19_kitchen)C++20
20 / 100
24 ms1092 KiB
#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\n";
            return 0;
        }
    }

    int BOUND = max(sumB, sumA) + 1;
    vi dp(BOUND, -INF);
    dp[0] = 0;

    F0R(i, n) {
        vi newDp = dp;

        F0R(j, BOUND) {
            if (j - a[i] >= 0) newDp[j] = max( dp[j - a[i]], dp[j]);
        }

        dp = newDp;
    }

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


    cout << "Impossible\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...