Submission #396462

#	Time	Username	Problem	Language	Result	Execution time	Memory
396462		KoD	Kitchen (BOI19_kitchen)	C++17	100 / 100	26 ms	972 KiB

kitchen

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr int MAX = 300 * 300;

int main() {
    int N, M, K;
    std::cin >> N >> M >> K;
    Vec<int> A(N);
    for (auto& x: A) {
        std::cin >> x;
        if (x < K) {
            std::cout << "Impossible\n";
            return 0;
        }
    }
    Vec<int> big, small;
    for (int i = 0; i < M; ++i) {
        int x;
        std::cin >> x;
        (x > N ? big : small).push_back(x);
    }
    std::array<int, MAX + 1> max;
    max.fill(-1);
    max[0] = 0;
    for (const auto x: big) {
        for (int i = MAX; i >= 0; --i) {
            if (max[i] == -1) {
                continue;
            }
            max[i + x] = std::max(max[i + x], max[i] + 1);
        }
    }
    std::bitset<MAX + 1> gain;
    gain.set(0);
    for (const auto x: small) {
        gain |= gain << x;
    }
    std::array<int, MAX + 1> lowb;
    lowb.fill(INF);
    for (int i = MAX; i >= 0; --i) {
        if (gain.test(i)) {
            lowb[i] = i;
        }
        if (i < MAX) {
            lowb[i] = std::min(lowb[i], lowb[i + 1]);
        }
    }
    const int whole = std::accumulate(A.begin(), A.end(), 0);
    int ans = INF;
    for (int i = 0; i <= MAX; ++i) {
        if (max[i] == -1) {
            continue;
        }
        const int rem1 = std::max(0, N * (K - max[i]));
        const int rem2 = std::max(0, whole - i);
        const int min = lowb[std::max(rem1, rem2)];
        if (min != INF) {
            ans = std::min(ans, min + i - whole);
        }
    }
    if (ans == INF) {
        std::cout << "Impossible\n";
    }
    else {
        std::cout << ans << '\n';
    }
    return 0;
}

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