#include <bits/stdc++.h>
using namespace std;
const int N = 302;
const int inf = 1000 * 1000 * 1000;
template<typename T>
istream& operator >> (istream& is, vector<T> &a) { for(T &element : a) is >> element; return is; }
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
#ifdef saarang
freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
#endif
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n), b(m);
cin >> a; cin >> b;
if(*min_element(a.begin(), a.end()) < k)
return cout << "Impossible" << '\n', 0;
vector<int> dp(N * N, -1);
dp[0] = 0;
for(int i = 0; i < m; i++) {
for(int j = m * N - b[i]; j >= 0; j--)
if(dp[j] != -1)
dp[j + b[i]] = max(dp[j + b[i]], dp[j] + min(b[i], n));
}
int answer = inf;
int sum = accumulate(a.begin(), a.end(), 0);
for(int i = sum; i < N * N; i++)
if(dp[i] >= n * k)
answer = min(answer, i - sum);
cout << (answer ^ inf ? to_string(answer) : "Impossible") << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Correct |
1 ms |
748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Correct |
1 ms |
748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
748 KB |
Output is correct |
| 9 |
Correct |
1 ms |
748 KB |
Output is correct |
| 10 |
Correct |
1 ms |
748 KB |
Output is correct |
| 11 |
Correct |
1 ms |
748 KB |
Output is correct |
| 12 |
Correct |
1 ms |
748 KB |
Output is correct |
| 13 |
Correct |
1 ms |
648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
748 KB |
Output is correct |
| 2 |
Correct |
26 ms |
748 KB |
Output is correct |
| 3 |
Correct |
53 ms |
748 KB |
Output is correct |
| 4 |
Correct |
73 ms |
748 KB |
Output is correct |
| 5 |
Correct |
60 ms |
748 KB |
Output is correct |
| 6 |
Correct |
21 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Correct |
1 ms |
748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
748 KB |
Output is correct |
| 9 |
Correct |
1 ms |
748 KB |
Output is correct |
| 10 |
Correct |
1 ms |
748 KB |
Output is correct |
| 11 |
Correct |
1 ms |
748 KB |
Output is correct |
| 12 |
Correct |
1 ms |
748 KB |
Output is correct |
| 13 |
Correct |
1 ms |
648 KB |
Output is correct |
| 14 |
Correct |
31 ms |
748 KB |
Output is correct |
| 15 |
Correct |
26 ms |
748 KB |
Output is correct |
| 16 |
Correct |
53 ms |
748 KB |
Output is correct |
| 17 |
Correct |
73 ms |
748 KB |
Output is correct |
| 18 |
Correct |
60 ms |
748 KB |
Output is correct |
| 19 |
Correct |
21 ms |
748 KB |
Output is correct |
| 20 |
Correct |
2 ms |
748 KB |
Output is correct |
| 21 |
Correct |
1 ms |
748 KB |
Output is correct |
| 22 |
Correct |
2 ms |
748 KB |
Output is correct |
| 23 |
Correct |
1 ms |
748 KB |
Output is correct |
| 24 |
Correct |
1 ms |
364 KB |
Output is correct |
| 25 |
Correct |
17 ms |
768 KB |
Output is correct |
| 26 |
Correct |
26 ms |
748 KB |
Output is correct |
| 27 |
Correct |
16 ms |
748 KB |
Output is correct |
| 28 |
Correct |
46 ms |
748 KB |
Output is correct |
| 29 |
Correct |
50 ms |
748 KB |
Output is correct |
| 30 |
Correct |
69 ms |
748 KB |
Output is correct |
