Submission #1151720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151720		dobri_oke	Kitchen (BOI19_kitchen)	C++20	9 / 100	1 ms	328 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;
    int a[n+1], b[m+1];
    int sum=0;
    bool b4=0;
    multiset < int > st;
    for(int i=1;i<=n;i++){ 
        cin >> a[i]; 
        sum+=a[i];
        if(a[i]==1) b4=1;
    }
    for(int i=1;i<=m;i++) cin >> b[i];
    if(k>m){
        cout << "Impossible";
        return 0;
    }
    sort(b+1, b+m+1);
    int ans=0;
    bool b2=0;
    if(k==1 && m==2){
        if(b[1]+b[2]-sum<0) cout << "Impossible";
        else if(b[1]-sum>=0) cout << b[1]-sum;
        else if(b[2]-sum>=0) cout << b[2]-sum;
        else cout << b[2]+b[1]-sum;
        return 0;
    }
    if(k==1){
        if(b[1]-sum<0) cout << "Impossible";
        else cout << b[1]-sum;
        return 0;
    }
    // nmk/64
    st.insert(b[1]-n);
    st.insert(b[2]-n);
    if(*st.begin()<0){
        cout << "Impossible";
        return 0;
    }
    for(int i=1;i<=n;i++){
        a[i]-=2;
        while(a[i]>0){
            int g=*st.rbegin();
            if(g==0){
                b2=1;
                break;
            }
            st.erase(st.find(g));
            st.insert(g-1);
            a[i]--;
        }
        if(b2==1) break;
    }
    ans=*st.begin()+*st.rbegin();
    if(b2==1 || b4==1) cout << "Impossible";
    else cout << ans;
    //cout << *st.begin()+*st.rbegin(); 
}

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