| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1190048 | crafticat | Kitchen (BOI19_kitchen) | C++20 | 0 ms | 0 KiB |
#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], 0);
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