# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1099280 |
2024-10-11T05:05:10 Z |
vjudge1 |
Kitchen (BOI19_kitchen) |
C++17 |
|
83 ms |
120600 KB |
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int maxn = 300 + 7;
const int LOG = 20;
const int ALP_BET = 26;
const long long base = 311;
const long long MOD = (long long)(1e9) + 7LL;
typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;
const int INF = (int)(1e9) + 7;
const int maxSum = (int)(1e5) + 7;
int n, k;
int a[maxn];
int sum_a;
int m;
int b[maxn];
int sum_b;
int dp[maxn][maxSum];
int ans = INF;
void solve_sub_2(){
// INIT
ans = INF;
// DUYET
int max_state = 1 << m;
for(int state = 1; state < max_state; ++state){
int sum = 0;
int sum_r = 0;
for(int i = 0; i < m; ++i) if(state & (1 << i)){
sum = sum + b[i + 1];
int val = b[i + 1] % n;
if(b[i + 1] >= n)
val = n;
sum_r = sum_r + val;
}
if(sum >= sum_a && sum_r >= n * k){
ans = min(ans, sum - sum_a);
}
}
if(ans == INF){
cout << "Impossible\n";
} else
cout << ans << "\n";
return;
}
void solve_sub_3(){
// INIT
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
// DP
for(int i = 0; i < m; ++i)
for(int sum = 0; sum <= sum_b; ++sum) if(dp[i][sum] == 1){
dp[i + 1][sum] = 1;
if(sum + b[i + 1] <= sum_b)
dp[i + 1][sum + b[i + 1]] = 1;
}
// ANS
ans = INF;
for(int sum = sum_a; sum <= sum_b; ++sum) if(dp[m][sum] == 1){
ans = min(ans, sum - sum_a);
}
if(ans == INF){
cout << "Impossible\n";
} else
cout << ans << "\n";
return;
}
void solve(){
// INIT
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
// DP
for(int i = 0; i < m; ++i)
for(int sum = 0; sum <= sum_b; ++sum) if(dp[i][sum] != -1){
dp[i + 1][sum] = max(dp[i + 1][sum], dp[i][sum]);
if(sum + b[i + 1] <= sum_b){
int val = b[i + 1] % n;
if(b[i + 1] >= n)
val = n;
dp[i + 1][sum + b[i + 1]] =
max(dp[i + 1][sum + b[i + 1]], dp[i][sum] + val);
}
}
// ANS
ans = INF;
for(int sum = sum_a; sum <= sum_b; ++sum) if(dp[m][sum] >= n * k){
ans = min(ans, sum - sum_a);
}
if(ans == INF){
cout << "Impossible\n";
} else
cout << ans << "\n";
return;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// READ
cin >> n >> m >> k;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 1; i <= m; ++i)
cin >> b[i];
// CHECK
bool ok = true;
for(int i = 1; i <= n; ++i) if(a[i] < k){
ok = false;
break;
}
if(ok == false){
cout << "Impossible\n";
return 0;
}
// INIT
sum_a = 0;
sum_b = 0;
for(int i = 1; i <= n; ++i){
sum_a = sum_a + a[i];
}
for(int i = 1; i <= m; ++i){
sum_b = sum_b + b[i];
}
// SUBTASK
if(m <= 15){
solve_sub_2();
} else
if(k == 1){
solve_sub_3();
} else
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
408 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
408 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
344 KB |
Output is correct |
11 |
Correct |
2 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
460 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
120588 KB |
Output is correct |
2 |
Correct |
47 ms |
120504 KB |
Output is correct |
3 |
Correct |
54 ms |
120400 KB |
Output is correct |
4 |
Correct |
59 ms |
120400 KB |
Output is correct |
5 |
Correct |
63 ms |
120600 KB |
Output is correct |
6 |
Correct |
46 ms |
120400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
120400 KB |
Output is correct |
2 |
Correct |
39 ms |
120412 KB |
Output is correct |
3 |
Correct |
43 ms |
120412 KB |
Output is correct |
4 |
Correct |
41 ms |
120544 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
408 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
344 KB |
Output is correct |
11 |
Correct |
2 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
460 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
51 ms |
120588 KB |
Output is correct |
15 |
Correct |
47 ms |
120504 KB |
Output is correct |
16 |
Correct |
54 ms |
120400 KB |
Output is correct |
17 |
Correct |
59 ms |
120400 KB |
Output is correct |
18 |
Correct |
63 ms |
120600 KB |
Output is correct |
19 |
Correct |
46 ms |
120400 KB |
Output is correct |
20 |
Correct |
42 ms |
120400 KB |
Output is correct |
21 |
Correct |
39 ms |
120412 KB |
Output is correct |
22 |
Correct |
43 ms |
120412 KB |
Output is correct |
23 |
Correct |
41 ms |
120544 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
63 ms |
120592 KB |
Output is correct |
26 |
Correct |
59 ms |
120468 KB |
Output is correct |
27 |
Correct |
49 ms |
120400 KB |
Output is correct |
28 |
Correct |
52 ms |
120596 KB |
Output is correct |
29 |
Correct |
66 ms |
120592 KB |
Output is correct |
30 |
Correct |
83 ms |
120400 KB |
Output is correct |