Submission #1199314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199314		dejameiniciar	Kitchen (BOI19_kitchen)	C++20	50 / 100	132 ms	8392 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n,m,k,s=0;
    cin>>n>>m>>k;
    if(k==1){
        vector<ll> V;
    for(ll i=0;i<n;i++){
        ll a;
        cin>>a;
        s+=a;
    }
    for(ll i=0;i<m;i++){
        ll a;
        cin>>a;
        V.push_back(a);
    }
    vector<ll> L(900001,0);
    L[0]=1;
    for(auto x:V){
        for(ll i=900000;i>=0;i--){
            if(L[i]==1){
                if(i+x<900001){
                    L[i+x]=1;
                }
            }
        }
    }
    ll ans=-1;
    for(ll i=s;i<900000;i++){
        if(L[i]==1){
            ans=i-s;
            break;
        }
    }
    if(ans==-1){
        cout<<"Impossible";
    }else{
        cout<<ans;
    }
    return 0;
    }
    vector<ll> V,L,dp1;
    vector<unordered_set<ll>> dp2;
    dp1.assign(90000,0);
    dp2.resize(90000);
    dp1[0]=1;
    dp2[0].insert(0);
    ll caja1=n*k;
    ll caja2=0;
    for(ll i=0;i<n;i++){
        ll a;
        cin>>a;
        if(a>=k){
            caja2+=a-k;
        }else{
            cout<<"Impossible";
            return 0;
        }
        L.push_back(a);
    }
    for(ll i=0;i<m;i++){
        ll a;
        cin>>a;
        V.push_back(a);
    }
    ll a,b,c;
    for(ll i=0;i<m;i++){
        for(ll j=90000;j>=0;j--){
            if(dp1[j]==1){
                b=caja1-j;
                if(V[i]>n){
                    a=n;
                    c=V[i]-n;
                }else{
                    a=V[i];
                    c=0;
                }
                if(a<=b){
                    dp1[j+a]=1;
                    for(auto x:dp2[j]){
                        dp2[j+a].insert(x+c);
                    }
                }else{
                    dp1[j+b]=1;
                    c+=a-b;
                    for(auto x:dp2[j]){
                        dp2[j+b].insert(x+c);
                    }
                }
            }
        }
    }
    ll ans=1000000000;
    for(auto x:dp2[n*k]){
        if(x<ans && x>=caja2){
            ans=x;
        }
    }
    if(ans!=1000000000){
        cout<<ans-caja2;
    }else{
        cout<<"Impossible";
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 0 / 28