# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
136743 |
2019-07-26T08:05:29 Z |
azatega |
Kitchen (BOI19_kitchen) |
C++11 |
|
192 ms |
110968 KB |
#include <iostream>
using namespace std;
int cost[310];
int chefs[310];
int memo[310][91000];
int main()
{
int n, m, k, sum = 0;
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> cost[i];
sum += cost[i];
}
for(int i = 0; i < m; i++)
cin >> chefs[i];
for(int i = 0; i < n; i++){
if(cost[i] < k){
cout << "Impossible" << endl;
return 0;
}
}
for(int i = 0; i < 310; i++)
for(int j = 0; j < 91000; j++)
memo[i][j] = -1;
for(int i = 0; i < 310; i++)
memo[i][0] = 0;
int najbolje = 99999997;
for(int i = 1; i <= m; i++){
for(int j = chefs[i - 1]; j < 91000; j++){
if(memo[i - 1][j] != -1)
memo[i][j] = memo[i - 1][j];
if(memo[i - 1][j - chefs[i - 1]] != -1)
memo[i][j] = max(memo[i][j], memo[i - 1][j - chefs[i - 1]] + min(chefs[i - 1], n));
if(j >= sum && memo[i][j] >= k*n){
najbolje = min(najbolje, j - sum);
}
}
}
if(najbolje != 99999997)
cout << najbolje << endl;
else
cout << "Impossible" << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
110840 KB |
Output is correct |
2 |
Correct |
98 ms |
110712 KB |
Output is correct |
3 |
Correct |
109 ms |
110728 KB |
Output is correct |
4 |
Correct |
98 ms |
110840 KB |
Output is correct |
5 |
Correct |
98 ms |
110772 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
98 ms |
110840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
110840 KB |
Output is correct |
2 |
Correct |
98 ms |
110712 KB |
Output is correct |
3 |
Correct |
109 ms |
110728 KB |
Output is correct |
4 |
Correct |
98 ms |
110840 KB |
Output is correct |
5 |
Correct |
98 ms |
110772 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
98 ms |
110840 KB |
Output is correct |
9 |
Correct |
99 ms |
110712 KB |
Output is correct |
10 |
Correct |
119 ms |
110652 KB |
Output is correct |
11 |
Correct |
118 ms |
110712 KB |
Output is correct |
12 |
Correct |
100 ms |
110668 KB |
Output is correct |
13 |
Incorrect |
100 ms |
110716 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
110776 KB |
Output is correct |
2 |
Correct |
143 ms |
110712 KB |
Output is correct |
3 |
Correct |
162 ms |
110868 KB |
Output is correct |
4 |
Correct |
185 ms |
110712 KB |
Output is correct |
5 |
Correct |
192 ms |
110684 KB |
Output is correct |
6 |
Correct |
153 ms |
110812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
110968 KB |
Output is correct |
2 |
Correct |
105 ms |
110768 KB |
Output is correct |
3 |
Correct |
105 ms |
110712 KB |
Output is correct |
4 |
Correct |
104 ms |
110696 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
98 ms |
110840 KB |
Output is correct |
2 |
Correct |
98 ms |
110712 KB |
Output is correct |
3 |
Correct |
109 ms |
110728 KB |
Output is correct |
4 |
Correct |
98 ms |
110840 KB |
Output is correct |
5 |
Correct |
98 ms |
110772 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
98 ms |
110840 KB |
Output is correct |
9 |
Correct |
99 ms |
110712 KB |
Output is correct |
10 |
Correct |
119 ms |
110652 KB |
Output is correct |
11 |
Correct |
118 ms |
110712 KB |
Output is correct |
12 |
Correct |
100 ms |
110668 KB |
Output is correct |
13 |
Incorrect |
100 ms |
110716 KB |
Output isn't correct |