제출 #762715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762715		zsombor	Kitchen (BOI19_kitchen)	C++17	100 / 100	50 ms	716 KiB

kitchen

#include <iostream>
#include <vector>
using namespace std;

int n, m, k, a, sum = 0;
vector <int> ks(1e5 + 1, -1e9);

int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> a;
        sum += a;
        if (a < k) { cout << "Impossible"; return 0; }
    }

    ks[0] = 0;
    for (int i = 0; i < m; i++) {
        cin >> a;
        for (int j = 1e5; j >= a; j--) {
            ks[j] = max(ks[j], ks[j - a] + min(a, n));
        }
    }

    for (int i = sum; i <= 1e5; i++) {
        if (ks[i] < n * k) continue;
        cout << i - sum;
        return 0;
    }
    cout << "Impossible";
}

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