oj.uz

Submission #945355

# Submission time Handle Problem Language Result Execution time Memory
945355 2024-03-13T16:45:44 Z LucaIlie Kitchen (BOI19_kitchen) C++17
0 / 100
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -