제출 #1304093

#제출 시각아이디문제언어결과실행 시간메모리
1304093exoworldgdKitchen (BOI19_kitchen)C++20
0 / 100
3 ms824 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\n",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,y=0; x+1; x--) {
            while (x+1 && !big[c][x]) x--;
            while (x+1 && y<M && (!small[y] || x+y<need)) y++;
            if (x+1 && y<M) res=min(res,x+y-need);
        }
        small>>=n;
    }
    if (res==M) cout << "Impossible\n";
    else cout << res << '\n';
}
#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...