Submission #1151829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151829		dobri_oke	Kitchen (BOI19_kitchen)	C++20	31 / 100	108 ms	432 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 = 1e3+100, NN=26, mod=1e9+7;
//int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); }
//int lcm(int a, int b) { return a / gcd(a, b) * b; }
//int binpow(int a,int b){if(!b)return 1; if(b&1)return a*binpow(a,b-1)%mod; int x=binpow(a,b/2); return x*x%mod;}
signed main(){   
    ios_base::sync_with_stdio(0);   
    cin.tie(0);   
    cout.tie(0);
    int n, m, k;
    
    cin >> n >> m >> k;
    
    bool b3 = 0;
    
    int a[n], b[m], sum = 0, ans = 1e18;
    
    for(int i = 0 ; i < n ; i++){
        cin >> a[i];
        
        if(a[i] < k) b3 = 1;
        
        sum += a[i];
    }
    
    bool b2=0;
    
    for(int i = 0 ; i < m ; i++) cin >> b[i];
    
    if(m < k || b3 == 1){
        cout << "Impossible";
        
        return 0;
    }
    
    sort(b, b+m);
    
    for(int mask = 0 ; mask < (1<<m) ; mask++){
        vector < int > v;
        for(int i = 0 ; i < m ; i++){
            if((mask>>i) & 1) v.pb(b[i]);
        }
        
        
        if(v.size() < k) continue;
        for(int i = 1; i <= n; i++){
            int g=v.size()-1, kk=k;
            while(kk--){
                v[g]--;
                g--;
            }
            sort(v.begin(), v.end());
        }
        
        int sum2=0;
        
        for(auto to : v) sum2+=to;
        
        if(sum2>=sum-(n*k) && v[0]>=0){
            b2=1;
            ans=min(ans, sum2-(sum-(n*k)));
        }
    }
    
    if(b2==1) cout << ans;
    else cout << "Impossible";
}

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