#include <bits/stdc++.h>
using namespace std;
#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define re resize
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loopr(i, n) for(int i = n-1; i >= 0; i--)
#define loop1(i, n) for(int i = 1; i <= n; i++)
#define print(x) cout << #x << ": " << x << endl << flush
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;
template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }
const int inf = 1e17;
const int maxv = 305*305;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vi a(n+1);
loop1(i, n) cin >> a[i];
int sum = 0;
loop1(i, n) sum += a[i];
vi b(m+1);
loop1(i, m) cin >> b[i];
sort(all1(b));
vi dp(maxv);
dp[0] = 1;
loop1(i, m) if(b[i] <= n) {
loopr(j, maxv-b[i]) {
dp[j+b[i]] |= dp[j];
}
}
loopr(j, maxv) {
if(j < n*k and dp[j]) dp[j] += (n*k - j + n-1) / n;
}
loop1(i, m) if(b[i] > n) {
loopr(j, maxv-b[i]) {
if(dp[j] >= 1 and dp[j+b[i]] == 0) {
dp[j+b[i]] = max(dp[j] - 1, 1ll);
} else if(dp[j] >= 1 and dp[j+b[i]] >= 1) {
ckmin(dp[j+b[i]], max(dp[j] - 1, 1ll));
}
}
}
int res = inf;
loop(j, maxv) if(j >= sum) if(dp[j] == 1) {
ckmin(res, j - sum);
}
loop1(i, n) if(a[i] < k) res = inf;
if(res == inf) cout << "Impossible" << endl;
else cout << res << endl;
}
signed main() {
fast_io;
int t = 1; //cin >> t;
while(t--)
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
2 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
2 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
980 KB |
Output is correct |
| 11 |
Correct |
4 ms |
960 KB |
Output is correct |
| 12 |
Correct |
5 ms |
956 KB |
Output is correct |
| 13 |
Correct |
6 ms |
980 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
69 ms |
980 KB |
Output is correct |
| 2 |
Correct |
62 ms |
980 KB |
Output is correct |
| 3 |
Correct |
72 ms |
980 KB |
Output is correct |
| 4 |
Correct |
82 ms |
980 KB |
Output is correct |
| 5 |
Correct |
69 ms |
980 KB |
Output is correct |
| 6 |
Correct |
57 ms |
980 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
980 KB |
Output is correct |
| 2 |
Correct |
7 ms |
980 KB |
Output is correct |
| 3 |
Correct |
11 ms |
980 KB |
Output is correct |
| 4 |
Correct |
12 ms |
980 KB |
Output is correct |
| 5 |
Correct |
12 ms |
980 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
2 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
980 KB |
Output is correct |
| 11 |
Correct |
4 ms |
960 KB |
Output is correct |
| 12 |
Correct |
5 ms |
956 KB |
Output is correct |
| 13 |
Correct |
6 ms |
980 KB |
Output is correct |
| 14 |
Correct |
69 ms |
980 KB |
Output is correct |
| 15 |
Correct |
62 ms |
980 KB |
Output is correct |
| 16 |
Correct |
72 ms |
980 KB |
Output is correct |
| 17 |
Correct |
82 ms |
980 KB |
Output is correct |
| 18 |
Correct |
69 ms |
980 KB |
Output is correct |
| 19 |
Correct |
57 ms |
980 KB |
Output is correct |
| 20 |
Correct |
3 ms |
980 KB |
Output is correct |
| 21 |
Correct |
7 ms |
980 KB |
Output is correct |
| 22 |
Correct |
11 ms |
980 KB |
Output is correct |
| 23 |
Correct |
12 ms |
980 KB |
Output is correct |
| 24 |
Correct |
12 ms |
980 KB |
Output is correct |
| 25 |
Correct |
13 ms |
980 KB |
Output is correct |
| 26 |
Correct |
34 ms |
980 KB |
Output is correct |
| 27 |
Correct |
28 ms |
964 KB |
Output is correct |
| 28 |
Correct |
49 ms |
980 KB |
Output is correct |
| 29 |
Correct |
32 ms |
980 KB |
Output is correct |
| 30 |
Correct |
72 ms |
980 KB |
Output is correct |
