Submission #1184516

#TimeUsernameProblemLanguageResultExecution timeMemory
1184516razivoKitchen (BOI19_kitchen)C++20
0 / 100
175 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;
    if(M<K) proper=false;
    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<=K) 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) {
        bi t = init<<b;
        init = t|init;
    }
    vector<bi> c(M);
    for (int i = 0; i < 90000; ++i) {
        if(init[i]) {
            c[i/K][i]=true;
        }
    }
    for(int b : v2) {
        c[M-1]=c[M-1]|(c[M-1]<<b);
        for (int i = M-2; i >-1; --i) {
            c[i+1]=c[i+1]|(c[i]<<b);
        }
    }
    for (int i = sum; i < 90000; ++i) {
        if(c[M-1][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...