Submission #1184521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184521		razivo	Kitchen (BOI19_kitchen)	C++20	0 / 100	206 ms	3744 KiB

kitchen

#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) {
        init = (init<<b)|init;
    }
    vector<bi> c(N+1);
    for (int i = 0; i < 90000; ++i) {
        if(init[i]) {
            c[i/K][i]=true;
        }
    }
    for(int b : v2) {
        c[N]=c[N]|(c[N]<<b);
        for (int i = N-1; i >-1; --i) {
            c[i+1]=c[i+1]|(c[i]<<b);
        }
    }
    for (int i = sum; i < 90000; ++i) {
        if(c[N][i]) {
            cout<<i-sum<<endl;
            exit(0);
        }
    }
    cout<<"Impossible"<<endl;
    exit(0);
}

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