Submission #1130158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130158		vladilius	Kitchen (BOI19_kitchen)	C++20	100 / 100	219 ms	3580 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, k; cin>>n>>m>>k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    vector<int> b(m);
    for (int i = 0; i < m; i++){
        cin>>b[i];
    }
    
    int S1 = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] < k){
            cout<<"Impossible"<<"\n";
            return 0;
        }
        S1 += a[i];
    }
    
    int S2 = k * n;
    
    sort(b.begin(), b.end());
    int j = 0;
    while (j < m && b[j] < n) j++;
    
    const int A = 90000;
    
    vector<bool> sm(A + 1); sm[0] = 1;
    for (int i = 0; i < j; i++){
        for (int t = A; t >= 0; t--){
            if (sm[t]){
                sm[t + b[i]] = 1;
            }
        }
    }
    
    vector<int> all;
    for (int i = 0; i <= A; i++){
        if (sm[i]) all.pb(i);
    }
    
    int M = m - j;
    bitset<90001> can[M + 1]; can[0][0] = 1;
    for (int i = j; i < m; i++){
        for (int t = M - 1; t >= 0; t--){
            can[t + 1] |= (can[t] << b[i]);
        }
    }
    
    int out = 1e9;
    for (int cc = 0; cc <= M; cc++){
        vector<int> low(A + 1, -1); low[A] = (can[cc][A]) ? A : -1;
        for (int i = A - 1; i >= 0; i--){
            if (!can[cc][i]){
                low[i] = low[i + 1];
            }
            else {
                low[i] = i;
            }
        }
        for (int sl: all){
            if (sl >= (S2 - n * cc)){
                int x = low[max(0, S1 - sl)];
                if (x != -1){
                    out = min(out, sl + x);
                }
            }
        }
    }
    if (out == 1e9){
        cout<<"Impossible"<<"\n";
    }
    else {
        cout<<out - S1<<"\n";
    }
}

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