Submission #1184523

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