Submission #1151874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151874		Robert_junior	Kitchen (BOI19_kitchen)	C++20	51 / 100	101 ms	724 KiB

kitchen

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
const int N = 303 * 303, M = 5e5 + 7;
int a[501], b[501], n, m, k;
int dp[N];
int check(vector<int>v){
    int sum = 0;
    if(v.size() < k) return -1;
    for(int i = n; i >= 1; i--){
        sort(all(v));
        int sz = v.size() - k;
        if(v[sz] <= 0){
            return -1;
        }
        sum+=a[i]-k;
        for(int j = v.size() - 1; j >= sz; j--){
            v[j]--;
        }
    }
    int res = 0;
    for(auto it : v) res += it;
    if(res < sum) return -1;
    return res - sum;
}
void solve(){
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        if(a[i] < k){
            cout<<"Impossible";
            return;
        }
    }
    dp[0] = 1;
    for(int i = 1; i <= m; i++){
        cin>>b[i];
        if(k == 1){
            for(int j = N - 1; j >= b[i]; j--){
                dp[j] |= dp[j - b[i]];
            }
        }
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    if(k == 1){
        int sum = 0;
        for(int i = 1; i <= n; i++) sum += a[i];
        for(int i = sum; i < N; i++){
            if(dp[i]){
                cout<<i - sum<<'\n';
                return;
            }
        }
        cout<<"Impossible";
        return;
    }
    int res = 1e9;
    for(int msk = 0; msk < (1<<m); msk++){
        vector<int>v;
        for(int i = 0; i < m; i++){
            if((msk>>i) & 1) continue;
            v.pb(b[i+1]);
        }
        int ok = check(v);
        if(ok != -1) res = min(res, ok);
    }
    if(res == 1e9) cout<<"Impossible";
    else cout<<res;
}
main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin>>t; 
    for(int i = 1; i <= t; i++){
        //cout<<"Case "<<i<<": ";
        solve();
    }
}

Compilation message (stderr)

kitchen.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main(){
      | ^~~~

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