Submission #1190049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190049		crafticat	Kitchen (BOI19_kitchen)	C++20	9 / 100	1092 ms	9464 KiB

kitchen

#include <bits/stdc++.h>

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

using ll =long long;
template<typename T>
using V = vector<T>;
using vi = V<ll>;

constexpr ll INF = 1e9;

ll eval(ll n, ll m, ll k, vi a, vi b) {
    ll sumB = 0, sumA = 0;

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

    F0R(i, m) {
        if (b[i] < k) {
            return -1;
        }
    }

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

    dp[0][0] = 0;
    FOR(i, 1, n + 1) {
        auto newDp = dp;

        FOR(j, 1, BOUND) {
            FOR(t, 0, k + 1) {
                if (j - a[i - 1] < 0) continue;

                ll oldSum = j - a[i - 1];
                if (t > 0 && dp[oldSum][t - 1] + a[i - 1] >= m)
                    newDp[j][t] = max(newDp[j][t], 0ll);

                newDp[j][t] = max(newDp[j][t], dp[oldSum][t] + a[i - 1]);
            }
        }

        dp = newDp;
    }

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

    return -1;
}

ll eval2(ll n, ll m, ll k, vi a, vi b) {
    ll sumB = 0, sumA = 0;

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

    F0R(i, m) {
        if (b[i] < k) {
            return -1;
        }
    }

    ll 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) {
            return i - sumB;
        }
    }


    return -1;
}

#ifndef DEBUG
int main() {
    ll n, m, k; cin >> n >> m >> k;

    vi a(n), b(m);

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

    ll res =  eval(n, m, k, a, b);
    if (res == -1)
        cout << "Impossible\n";
    else
        cout << res << "\n";
}
#endif
#if DEBUG
ll rand(ll a, ll b) {
    return a + rand() % (b - a + 1);
}

ll main() {
    ll test = 0;
    while (1) {
        test++;
        ll n = rand(1 ,50), m = rand(1, 50), k = 1;

        vi a(n), b(m);

        F0R(i, n)
            a[i] = rand(1, 50);
        F0R(i, m)
            b[i] = rand(1, 50);
        swap(a, b);
        swap(m, n);

        ll v1 = eval(n, m, k, a, b);
        ll v2 = eval2(n, m, k, a, b);

        if (v1 != v2) {
            ll stop = 25;
            eval2(n, m, k, a, b);
            eval(n, m, k, a, b);
        } else {
            cout << "succ";
        }
    }
}
#endif

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