oj.uz

Submission #945351

# Submission time Handle Problem Language Result Execution time Memory
945351 2024-03-13T16:43:02 Z LucaIlie Kitchen (BOI19_kitchen) C++17
0 / 100
 21 ms 856 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;
        }
    }

    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 1 ms 604 KB Output is correct
2 Correct 1 ms 700 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 796 KB Output is correct
2 Correct 15 ms 600 KB Output is correct
3 Correct 20 ms 600 KB Output is correct
4 Correct 20 ms 604 KB Output is correct
5 Incorrect 19 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

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