Submission #1151895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151895		Robert_junior	Kitchen (BOI19_kitchen)	C++20	100 / 100	19 ms	584 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;
        }
    }
    for(int i = 0; i < N; i++) dp[i] = -1;
    dp[0] = 0;
    for(int i = 1; i <= m; i++){
        cin>>b[i];
        for(int j = N - 1; j >= b[i]; j--){
            if(dp[j - b[i]] == -1) continue;
            if(dp[j] == -1) dp[j] = dp[j - b[i]] + min(b[i], n);
            else dp[j] = max(dp[j - b[i]] + min(b[i], n), dp[j]);
        }
    }
    int sum = 0;
    for(int i = 1; i <= n; i++) sum += a[i];
    for(int i = sum; i < N; i++){
        if(dp[i] >= n * k){
            cout<<i - sum<<'\n';
            return;
        }
    }
    cout<<"Impossible";
}
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:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main(){
      | ^~~~

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