제출 #1151944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151944		dobri_oke	Kitchen (BOI19_kitchen)	C++20	21 / 100	20 ms	836 KiB

kitchen

//#pragma GCC target ("avx2")   
//#pragma GCC optimize ("Ofast")

#include <bits/stdc++.h>   
using namespace std;

#define int long long  
#define F first 
#define S second 
#define pb push_back

const int N = 1e6+100, NN=26, mod=1e9+7;

int dp[N];

signed main(){   
    
    ios_base::sync_with_stdio(0);
    
    cin.tie(0);
    
    cout.tie(0);
    
    int n, m, k;
    
    cin >> n >> m >> k;
    
    int a[n + 1], b[m + 1], sum=0, sum2=0;
    
    bool b2=0;
    
    for(int i = 1 ; i <= n ; ++i) { 
        
        cin >> a[i];
        
        sum2+=a[i];   
        
        if(a[i]<k) b2=1;
        
    }
    
    if(b2 == 1 || k > m) {
        cout << "Impossible";
        
        return 0;
    }
    
    for(int i = 1 ; i <= sum ; ++i) dp[i] = -1e18;
    
    for(int i = 1 ; i <= m ; ++i){ 
        
        cin >> b[i];
        
        sum+=b[i];
        
    }
    
    for(int i = 1 ; i <= m ; ++i) {
        
        for(int j = sum-b[i]; j >= 0; --j) {
            if(dp[j]!=-1e18) dp[j + b[i]] = max(dp[j + b[i]], dp[j] + min(n, b[i]));
        }
        
    }
    
    int ans=1e18;
    
    for(int i = sum2 ; i <= sum ; ++i) {
        if(dp[i]>=n*k){
            ans=i;
            break;
        }
    }
    
    if(ans==1e18) cout << "Impossible";
    else cout << ans-sum2;
}

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