Submission #1151853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151853		dobri_oke	Kitchen (BOI19_kitchen)	C++20	31 / 100	103 ms	656 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;
    
    if(m <= 15){
    
        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";
        return 0;
    }
    
    int a[n + 1],  b[m + 1], cnt=0, cnt2=0;
    
    for(int i = 1 ; i <= n ; i++){ 
        
        cin >> a[i];
        
        cnt2+=a[i];   
    }
    
    for(int i = 1 ; i <= m ; i++){ 
        cin >> b[i];
        
        cnt+=b[i];   
    }
    
    map < int , int > mp;
    
    for(int i=1;i<=m;i++){
        int sum=b[i];
        
        mp[sum]=1;
        
        for(int j=i+1;j<=m;j++){
            sum+=b[j];
            mp[sum]=1;
        }
    }
    
    int ans=1e18;
    
    for(int i=cnt2;i<=cnt;i++){
        if(mp[i]==1){
            ans=i;
            break;
        }
    }
    if(ans==1e18) cout << "Impossible";
    else cout << ans-cnt2;
}

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