Submission #1304090

#TimeUsernameProblemLanguageResultExecution timeMemory
1304090exoworldgdKitchen (BOI19_kitchen)C++20
52 / 100
1096 ms832 KiB
#pragma GCC optimize("O5,unroll-loops,inline,fast-math")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0)
#define int long long
using namespace std;
const int N=305,M=90005;
int n,m,k,a[N],b[N],need=0,res=M;
bitset<M> small,big[N];
signed main(void) {
    exoworldgd;
    cin >> n >> m >> k;
    for (int i=0; i<n; i++) cin >> a[i];
    for (int i=0; i<m; i++) cin >> b[i];
    sort(b,b+m);
    for (int i=0; i<n; i++) {
        if (a[i]<k) return cout << "Impossible",0;
        need+=a[i]-k;
    }
    small[0]=1;
    for (int i=0; i<m && b[i]<n; i++) small|=small<<b[i];
    big[0][0]=1;
    for (int i=m-1; i+1 && b[i]>=n; i--) {
        for (int c=min(m,k); c; c--) {
            bitset<M> add=big[c-1]<<(b[i]-n);
            big[c]|=add|(big[c]<<b[i]);
        }
    }
    for (int c=k; c+1; c--) {
        for (int x=M-1; x+1; x--) {
            if (!big[c][x]) continue;
            for (int y=0; y<M; y++) if (small[y] && x+y>=need) {res=min(res,x+y-need); break;}
        }
        small>>=n;
    }
    if (res==M) cout << "Impossible";
    else cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...