# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
762169 | 2023-06-21T03:07:27 Z | anha3k25cvp | Kitchen (BOI19_kitchen) | C++14 | 1000 ms | 69948 KB |
#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define dl double #define st first #define nd second #define II pair <int, int> using namespace std; const int N = 5 + 1e5; const int inf = 7 + 1e9; vector <int> a; vector <vector <int>> f; int main() { #define TASKNAME "" ios_base :: sync_with_stdio (0); cin.tie (0); if ( fopen( TASKNAME".inp", "r" ) ) { freopen (TASKNAME".inp", "r", stdin); freopen (TASKNAME".out", "w", stdout); } int n, m, k; cin >> n >> m >> k; int val = 0; for (int i = 1; i <= n; i ++) { int x; cin >> x; if (x < k) { cout << "Impossible"; return 0; } val += x; } int ma = 0; a.assign(m + 1, 0); for (int i = 1; i <= m; i ++) { cin >> a[i]; ma += a[i]; } sort(a.begin() + 1, a.begin() + m + 1, greater <> ()); f.assign(ma + 1, vector <int> (m + 1, -1)); f[0][0] = 0; int ans = inf; for (int num = 0; num <= m; num ++) for (int sum = ma; sum >= 0; sum --) for (int i = num; i >= 0; i --) if (f[sum][i] >= 0) { if (num < m) f[sum + a[num + 1]][i + 1] = max(f[sum + a[num + 1]][i + 1], f[sum][i] + ((i + 1) % k == 0 ? a[num + 1] : 0)); if (sum >= val && f[sum][i] >= n) ans = min(ans, sum - val); } if (ans < inf) cout << ans; else cout << "Impossible"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 316 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 324 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 292 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 316 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 324 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 292 KB | Output is correct |
9 | Correct | 1 ms | 596 KB | Output is correct |
10 | Correct | 1 ms | 596 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Incorrect | 1 ms | 340 KB | Output isn't correct |
13 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1068 ms | 69948 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 468 KB | Output is correct |
2 | Incorrect | 2 ms | 468 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 316 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 324 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 292 KB | Output is correct |
9 | Correct | 1 ms | 596 KB | Output is correct |
10 | Correct | 1 ms | 596 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Incorrect | 1 ms | 340 KB | Output isn't correct |
13 | Halted | 0 ms | 0 KB | - |