Submission #1151944

#TimeUsernameProblemLanguageResultExecution timeMemory
1151944dobri_okeKitchen (BOI19_kitchen)C++20
21 / 100
20 ms836 KiB
//#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;
}
#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...