Submission #945355

#	Time	Username	Problem	Language	Result	Execution time	Memory
945355		LucaIlie	Kitchen (BOI19_kitchen)	C++17	0 / 100	1 ms	348 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;
        }
    }

    int wasted = MAX_S + 1;
    for ( int mask = 0; mask < (1 << m); mask++ ) {
        int sumB = 0, sumBN = 0;
        for ( int i = 0; i < m; i++ ) {
            if ( (mask >> i) & 1 ) {
                sumB += b[i];
                sumBN += min( b[i], n );
            }
        }
        if ( sumB >= sumA && sumBN >= n * k )
            wasted = min( wasted, sumB - sumA );
    }

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

    /*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: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28