Submission #535597

#	Time	Username	Problem	Language	Result	Execution time	Memory
535597		__Variatto	Kitchen (BOI19_kitchen)	C++17	100 / 100	31 ms	680 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=9e4+10;
int n, m, k, dp[MAX], a, b, suma;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++){
        cin>>a;
        if(a<k){
            cout<<"Impossible\n";
            return 0;
        }
        suma+=a;
    }
    int mini=MAX;
    for(int i=1; i<=MAX-2; i++)
        dp[i]=-1;
    for(int i=1; i<=m; i++){
        cin>>b;
        for(int j=MAX-2; j>=b; j--){
            if(dp[j-b]!=-1){
                dp[j]=max(dp[j], dp[j-b]+min(n, b));
                if(j>=suma && dp[j]>=n*k)
                    mini=min(mini, j);
            }
        }
    }
    if(mini==MAX)
        cout<<"Impossible\n";
    else
        cout<<mini-suma<<"\n";
}

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