# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
522776 | LucaDantas | Kitchen (BOI19_kitchen) | C++17 | 22 ms | 588 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
constexpr int maxn = 310, inf = 0x3f3f3f3f;
int a[maxn], b[maxn], ex[maxn];
int dp[maxn*maxn];
int main() {
int n, m, k; scanf("%d %d %d", &n, &m, &k);
for(int i = 0; i < n; i++)
scanf("%d", a+i);
for(int i = 0; i < m; i++)
scanf("%d", b+i);
int soma = 0;
for(int i = 0; i < n; i++) {
soma += a[i];
if(a[i] < k) return puts("impossible"), 0;
}
auto max = [](int a, int b) { return a > b ? a : b; };
auto min = [](int a, int b) { return a < b ? a : b; };
int max_val = 0;
for(int i = 0; i < m; i++)
max_val += b[i];
for(int i = 0; i <= max_val; i++)
dp[i] = -inf;
dp[0] = 0;
for(int i = 0; i < m; i++)
for(int j = max_val-b[i]; j >= 0; j--)
dp[j+b[i]] = max(dp[j+b[i]], dp[j] + min(n, b[i]));
int ans = -1;
for(int i = soma; i <= max_val; i++)
if(dp[i] >= n*k) { ans = i - soma; break; }
if(ans == -1) puts("impossible");
else printf("%d\n", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |