Submission #1352781

#TimeUsernameProblemLanguageResultExecution timeMemory
1352781NewtonabcKitchen (BOI19_kitchen)C++20
100 / 100
9 ms780 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dp[N],a[N],b[N];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,k; cin>>n >>m >>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    int mn=*min_element(a+1,a+n+1),sum=0,wt=0;
    for(int i=1;i<=n;i++) wt+=a[i];
    for(int i=1;i<=m;i++) sum+=b[i];
    if(mn<k){
        cout<<"Impossible";
        return 0;
    }
    dp[0]=0;
    for(int i=1;i<=sum;i++) dp[i]=INT_MIN;
    for(int i=1;i<=m;i++){
        for(int j=sum;j>=b[i];j--){
            dp[j]=max(dp[j],dp[j-b[i]]+min(n,b[i]));
        }
    }
    int ans=INT_MAX;
    for(int i=sum;i>=wt;i--){
        if(dp[i]>=n*k) ans=min(ans,i);
    }
    if(ans==INT_MAX) cout<<"Impossible";
    else cout<<ans-wt;
}
#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...