제출 #388137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388137		leaked	Kitchen (BOI19_kitchen)	C++14	100 / 100	113 ms	708 KiB

kitchen

#include <bits/stdc++.h>
//#pra
#define sz(x) (int)x.size()
#define vec vector
#define pb push_back
using namespace std;
const int N=3e2+3;
auto rnd=bind(uniform_int_distribution<int>(1,5),mt19937(time(0)));
int dp[N*N];
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=0;i<2;i++){
        fill(dp,dp+N*N,-1e9);
    }
    vec<int>a(n),b(m);
    int sm=0;
    for(auto &z : a ) cin>>z,sm+=z;
    for(auto &z : b) cin>>z;
    for(int i=0;i<n;i++){
        if(a[i]<k){
            cout<<"Impossible";
            return 0;
        }
    }
    sort(b.rbegin(),b.rend());
    dp[0]=0;
    int ans=2e9;
    for(int i=0;i<=m;i++){
        for(int s=N*N-1;s>=0;s--){
            if(i!=m && s+b[i]<N*N)dp[s+b[i]]=max(dp[s+b[i]],dp[s]+min(b[i],n));
//            cerr<<s<<' '<<dp[0][s]<<endl;
            if(s>=sm && dp[s]>=n*k){
//                cout<<i;
                ans=min(ans,s-sm);
//                cerr<<dp[1][s]<<' '<<s<<endl;
//                return 0;
            }
        }
//        swap(dp[0],dp[1]);
    }
    if(ans==2e9)
        cout<<"Impossible";
    else cout<<ans;
    return 0;
}

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