# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
124876 |
2019-07-04T05:04:03 Z |
구재현(#3056) |
Kitchen (BOI19_kitchen) |
C++14 |
|
139 ms |
120568 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
using lint = long long;
using pi = pair<lint, int>;
int n, m, k;
int a[MAXN], b[MAXN];
int dp1[100000];
int dp2[100000];
int nxt[100000][MAXN];
int main(){
cin >> n >> m >> k;
for(int i=1; i<=n; i++){
cin >> a[i];
if(a[i] < k){
puts("Impossible");
return 0;
}
}
for(int i=1; i<=m; i++) cin >> b[i];
sort(b + 1, b + m + 1);
int acc = accumulate(a + 1, a + n + 1, 0);
int l = lower_bound(b + 1, b + m + 1, n) - b;
dp1[0] = 1;
for(int i=1; i<l; i++){
for(int j=99999; j>=b[i]; j--){
dp1[j] |= dp1[j - b[i]];
}
}
dp2[0] = 0;
fill(dp2 + 1, dp2 + 100000, -1e9);
for(int i=l; i<=m; i++){
for(int j=99999; j>=b[i]; j--){
dp2[j] = max(dp2[j], dp2[j - b[i]] + 1);
}
}
fill(nxt[99999], nxt[99999] + k + 1, 99999);
for(int i=99998; i>=0; i--){
for(int j=max(0,dp2[i]); j<=k; j++) nxt[i][j] = nxt[i+1][j];;
for(int j=0; j<=dp2[i]; j++) nxt[i][j] = i;
}
int ret = 1e9;
for(int i=0; i<100000; i++){
if(!dp1[i]) continue;
int reqCnt = 0;
if(i < n * k){
reqCnt = (n * k - i + n - 1) / n;
}
int occNxt = nxt[max(0, acc - i)][reqCnt];
if(occNxt < 99998) ret = min(ret, i + occNxt);
}
if(ret > 1e8) puts("Impossible");
else cout << ret - acc << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
120056 KB |
Output is correct |
2 |
Correct |
91 ms |
120056 KB |
Output is correct |
3 |
Correct |
89 ms |
120056 KB |
Output is correct |
4 |
Correct |
91 ms |
120056 KB |
Output is correct |
5 |
Correct |
90 ms |
120440 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
89 ms |
120116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
120056 KB |
Output is correct |
2 |
Correct |
91 ms |
120056 KB |
Output is correct |
3 |
Correct |
89 ms |
120056 KB |
Output is correct |
4 |
Correct |
91 ms |
120056 KB |
Output is correct |
5 |
Correct |
90 ms |
120440 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
89 ms |
120116 KB |
Output is correct |
9 |
Correct |
91 ms |
120064 KB |
Output is correct |
10 |
Correct |
91 ms |
120028 KB |
Output is correct |
11 |
Correct |
92 ms |
120440 KB |
Output is correct |
12 |
Correct |
91 ms |
120440 KB |
Output is correct |
13 |
Correct |
112 ms |
120568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
111 ms |
120412 KB |
Output is correct |
2 |
Correct |
106 ms |
120480 KB |
Output is correct |
3 |
Correct |
118 ms |
120504 KB |
Output is correct |
4 |
Correct |
114 ms |
120540 KB |
Output is correct |
5 |
Correct |
111 ms |
120440 KB |
Output is correct |
6 |
Correct |
103 ms |
120568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
120508 KB |
Output is correct |
2 |
Correct |
95 ms |
120412 KB |
Output is correct |
3 |
Correct |
108 ms |
120432 KB |
Output is correct |
4 |
Correct |
95 ms |
120536 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
120056 KB |
Output is correct |
2 |
Correct |
91 ms |
120056 KB |
Output is correct |
3 |
Correct |
89 ms |
120056 KB |
Output is correct |
4 |
Correct |
91 ms |
120056 KB |
Output is correct |
5 |
Correct |
90 ms |
120440 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
89 ms |
120116 KB |
Output is correct |
9 |
Correct |
91 ms |
120064 KB |
Output is correct |
10 |
Correct |
91 ms |
120028 KB |
Output is correct |
11 |
Correct |
92 ms |
120440 KB |
Output is correct |
12 |
Correct |
91 ms |
120440 KB |
Output is correct |
13 |
Correct |
112 ms |
120568 KB |
Output is correct |
14 |
Correct |
111 ms |
120412 KB |
Output is correct |
15 |
Correct |
106 ms |
120480 KB |
Output is correct |
16 |
Correct |
118 ms |
120504 KB |
Output is correct |
17 |
Correct |
114 ms |
120540 KB |
Output is correct |
18 |
Correct |
111 ms |
120440 KB |
Output is correct |
19 |
Correct |
103 ms |
120568 KB |
Output is correct |
20 |
Correct |
95 ms |
120508 KB |
Output is correct |
21 |
Correct |
95 ms |
120412 KB |
Output is correct |
22 |
Correct |
108 ms |
120432 KB |
Output is correct |
23 |
Correct |
95 ms |
120536 KB |
Output is correct |
24 |
Correct |
2 ms |
256 KB |
Output is correct |
25 |
Correct |
124 ms |
120436 KB |
Output is correct |
26 |
Correct |
127 ms |
120500 KB |
Output is correct |
27 |
Correct |
113 ms |
120484 KB |
Output is correct |
28 |
Correct |
119 ms |
120440 KB |
Output is correct |
29 |
Correct |
139 ms |
120184 KB |
Output is correct |
30 |
Correct |
134 ms |
120496 KB |
Output is correct |