Submission #945358

#	Time	Username	Problem	Language	Result	Execution time	Memory
945358		LucaIlie	Kitchen (BOI19_kitchen)	C++17	100 / 100	20 ms	796 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300;
const int MAX_M = 300;
const int MAX_S = 9e4;
int a[MAX_N], b[MAX_M], maxSum[MAX_S + 1];

int main() {
    int n, m, k;

    cin >> n >> m >> k;
    for ( int i = 0; i < n; i++ )
        cin >> a[i];
    for ( int i = 0; i < m; i++ )
        cin >> b[i];

    if ( m < k ) {
        cout << "Impossible\n";
        return 0;
    }

    int sumA = 0;
    for ( int i = 0; i < n; i++ ) {
        sumA += a[i];
        if ( a[i] < k ) {
            cout << "Impossible\n";
            return 0;
        }
    }

    for ( int s = 0; s <= MAX_S; s++ )
        maxSum[s] = -MAX_S - 1;
    maxSum[0] = 0;
    for ( int i = 0; i < m; i++ ) {
        for ( int s = MAX_S; s >= b[i]; s-- )
            maxSum[s] = max( maxSum[s], maxSum[s - b[i]] + min( b[i], n ) );
    }

    int wasted = 0;
    while ( sumA + wasted <= MAX_S && maxSum[sumA + wasted] < n * k )
        wasted++;

    if ( sumA + wasted > MAX_S )
        cout << "Impossible\n";
    else
        cout << wasted;

    return 0;
}

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