Submission #1184533

#TimeUsernameProblemLanguageResultExecution timeMemory
1184533razivoKitchen (BOI19_kitchen)C++20
100 / 100
139 ms3344 KiB
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;
typedef bitset<90000> bi;
int main() {
    vector<int> v1;
    vector<int> v2;

    int sum  = 0;
    bool proper = true;
    int N,M,K; cin>>N>>M>>K;
    int sumK = N;
    for (int i = 0; i < N; ++i) {
        int a; cin>>a;
        if(a<K)proper = false;
        sum+=a;
    }
    for (int i = 0; i < M; ++i) {
        int b; cin>>b;
        if(b<=N) v1.push_back(b);
        else v2.push_back(b);
    }
    if(!proper) {
        cout<<"Impossible"<<endl;
        exit(0);
    }
    bi init;
    init[0]=true;
    for (int b : v1) {
        init = (init<<b)|init;
    }
    vector<bi> c(K+1);
    for (int i = 0; i < 90000; ++i) {
        if(init[i]) {
            c[min(i/N,K)][i]=true;
        }
    }
    for(int b : v2) {
        c[K]=c[K]|(c[K]<<b);
        for (int i = K-1; i >-1; --i) {
            c[i+1]=c[i+1]|(c[i]<<b);
        }
    }
    for (int i = sum; i < 90000; ++i) {
        if(c[K][i]) {
            cout<<i-sum<<endl;
            exit(0);
        }
    }
    cout<<"Impossible"<<endl;
    exit(0);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...