Submission #1351859

#TimeUsernameProblemLanguageResultExecution timeMemory
1351859WarinchaiKitchen (BOI19_kitchen)C++20
100 / 100
64 ms2392 KiB
#include<bits/stdc++.h>
using namespace std;

const int MX=500*500;
int a[505];
int b[505];
int dp[2][MX+5];
int inf=1e9;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k;cin>>n>>m>>k;
    int sum=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    int cant=0;
    for(int i=1;i<=n;i++)if(a[i]<k)cant=1;
    if(cant){
        cout<<"Impossible\n";
        return 0;
    }
    for(int i=0;i<=MX;i++)dp[0][i]=dp[1][i]=-inf;
    dp[0][0]=0;
    int cur=0;
    for(int i=1;i<=m;i++){
        cur^=1;
        for(int j=0;j<=MX;j++)dp[cur][j]=dp[cur^1][j];
        for(int j=0;j<=MX;j++){
            if(j+b[i]<=MX)dp[cur][j+b[i]]=max(dp[cur][j+b[i]],dp[cur^1][j]+min(n,b[i]));
        }
    }
    int ans=inf;
    for(int i=sum;i<=MX;i++){
        if(dp[cur][i]>=n*k){
            //cerr<<"at "<<i<<" "<<dp[cur][i]<<"\n";
            ans=min(ans,i-sum);
        }
    }
    if(ans!=inf){
        cout<<ans;
    }else{
        cout<<"Impossible";
    }
    return 0;
}
#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...