| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 771554 | Wael | Kitchen (BOI19_kitchen) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
//#define int long long
#define F first
#define S second
#define endl '\n'
#define INT INT_MAX
int const M = 301 , Mx = 1e5 , N = 4e6 + 2 , lg = 30 , mod = 1e9 + 7;
int dx[] = {0 , 0 , -1 , 1 , 1 , 1 , -1 , -1};
int dy[] = {1 , -1 , 0 , 0 , 1 , -1 , 1 , -1};
int T , n , m , k , x , ans = 1e9 , y , w , sum , a[M] , b[M] , mx = 9e4 , dp[4][Mx];
bool Dp[2][Mx][M];
int closer[Mx][M] , sum1;
main() {
ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; ++i) cin >> a[i] , sum += a[i];
for(int i = 1 ; i <= m ; ++i) cin >> b[i] , sum1 += b[i];
for(int i = 1 ; i <= n ; ++i) {
if(a[i] < k) {
cout << "Impossible" << endl;
return 0;
}
}
sort(b + 1 , b + m + 1);
int Index = lower_bound(b + 1 , b + m + 1 , n) - b; --Index;
dp[0][0] = 1;
for(int i = 1 ; i <= Index ; ++i) {
int I = (i % 2);
dp[I][0] = 1;
for(int j = 1 ; j <= mx ; ++j) {
dp[I][j] = dp[!I][j];
if(j >= b[i]) dp[I][j] = max(dp[I][j] , dp[!I][j - b[i]]);
}
}
Dp[Index % 2][0][0] = 1;
for(int i = Index + 1 ; i <= m ; ++i) {
int I = (i % 2);
Dp[I][0][0] = 1;
for(int j = 1 ; j <= sum1 ; ++j) {
for(int cnt = 1 ; cnt <= m - Index ; ++cnt) {
Dp[I][j][cnt] = Dp[!I][j][cnt];
if(j >= b[i]) Dp[I][j][cnt] = max(Dp[I][j][cnt] , Dp[!I][j - b[i]][cnt - 1]);
}
}
}
int I = m % 2;
for(int cnt = 1 ; cnt <= m - Index ; ++cnt) {
for(int j = mx ; j >= 1 ; --j) {
closer[j][cnt] = closer[j + 1][cnt];
if(Dp[I][j][cnt]) closer[j][cnt] = j;
}
}
for(int Left = 0 ; Left <= mx ; ++Left) {
if(dp[Index % 2][Left]) {
if(Left >= sum) ans = min(ans , Left - sum);
else {
int ReqCnt = k - (Left / n);
ReqCnt = max(ReqCnt , 0ll);
int ReqJ = sum - Left;
for(int CurCnt = ReqCnt ; CurCnt <= m - Index ; ++CurCnt)
if(closer[ReqJ][CurCnt]) ans = min(ans , (Left + closer[ReqJ][CurCnt]) - sum);
}
}
}
if(ans == 1e18) cout << "Impossible" << endl;
else cout << ans << endl;
return 0;
}