# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
124849 | 2019-07-04T04:18:20 Z | 임유진(#3051) | Kitchen (BOI19_kitchen) | C++14 | 131 ms | 100216 KB |
#include<stdio.h> #include<algorithm> using namespace std; #define MAXN 305 #define MAXSB 100000 const int INF = 1 << 30; int A[MAXN], B[MAXN]; int dp[MAXN][MAXSB]; int main() { int N, M, K; int mina = 300, suma = 0, sumb = 0; 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); for(int i = 0; i < N; i++) { mina = min(mina, A[i]); suma += A[i]; } for(int i = 0; i < M; i++) sumb += B[i]; //printf("mina = %d, suma = %d, sumb = %d\n", mina, suma, sumb); if(mina < K) { printf("Impossible"); return 0; } for(int i = 0; i < M; i++) for(int j = 0; j <= sumb; j++) dp[i][j] = -INF; dp[0][0] = 0; dp[0][B[0]] = min(B[0], N); for(int i = 1; i < M; i++) for(int j = 0; j <= sumb; j++) { dp[i][j] = dp[i - 1][j]; if(j >= B[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - B[i]] + min(B[i], N)); } /* for(int i = 0; i < M; i++){ for(int j = 0; j <= sumb; j++) printf("%d ", dp[i][j]); printf("\n"); } */ for(int i = suma; i <= sumb; i++) if(dp[M - 1][i] >= N * K) { printf("%d", i - suma); return 0; } printf("Impossible"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 632 KB | Output is correct |
10 | Correct | 2 ms | 504 KB | Output is correct |
11 | Correct | 2 ms | 424 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 91 ms | 68728 KB | Output is correct |
2 | Correct | 68 ms | 51452 KB | Output is correct |
3 | Correct | 76 ms | 57944 KB | Output is correct |
4 | Correct | 128 ms | 98384 KB | Output is correct |
5 | Correct | 129 ms | 98524 KB | Output is correct |
6 | Correct | 55 ms | 41976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 632 KB | Output is correct |
2 | Correct | 2 ms | 632 KB | Output is correct |
3 | Correct | 2 ms | 632 KB | Output is correct |
4 | Correct | 2 ms | 760 KB | Output is correct |
5 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 256 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 632 KB | Output is correct |
10 | Correct | 2 ms | 504 KB | Output is correct |
11 | Correct | 2 ms | 424 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 632 KB | Output is correct |
14 | Correct | 91 ms | 68728 KB | Output is correct |
15 | Correct | 68 ms | 51452 KB | Output is correct |
16 | Correct | 76 ms | 57944 KB | Output is correct |
17 | Correct | 128 ms | 98384 KB | Output is correct |
18 | Correct | 129 ms | 98524 KB | Output is correct |
19 | Correct | 55 ms | 41976 KB | Output is correct |
20 | Correct | 2 ms | 632 KB | Output is correct |
21 | Correct | 2 ms | 632 KB | Output is correct |
22 | Correct | 2 ms | 632 KB | Output is correct |
23 | Correct | 2 ms | 760 KB | Output is correct |
24 | Correct | 2 ms | 256 KB | Output is correct |
25 | Correct | 68 ms | 50332 KB | Output is correct |
26 | Correct | 82 ms | 62328 KB | Output is correct |
27 | Correct | 26 ms | 18936 KB | Output is correct |
28 | Correct | 68 ms | 51320 KB | Output is correct |
29 | Correct | 92 ms | 70008 KB | Output is correct |
30 | Correct | 131 ms | 100216 KB | Output is correct |