oj.uz

Submission #136738

# Submission time Handle Problem Language Result Execution time Memory
136738 2019-07-26T07:58:23 Z azatega Kitchen (BOI19_kitchen) C++11
29 / 100
 153 ms 110824 KB 
#include <iostream>

using namespace std;

int cost[310];
int chefs[310];
int memo[310][91000];



int main()
{
    int n, m, k, sum = 0;
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++){
        cin >> cost[i];
        sum += cost[i];
    }
    for(int i = 0; i < m; i++)
        cin >> chefs[i];

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

    for(int i = 0; i < 310; i++)
        for(int j = 0; j < 91000; j++)
            memo[i][j] = -1;

    for(int i = 0; i < 310; i++)
        memo[i][0] = 0;

    int najbolje = 99999997;

    for(int i = 1; i <= m; i++){
        for(int j = chefs[i - 1]; j < 91000; j++){
            if(memo[i - 1][j] != -1)
                memo[i][j] = memo[i - 1][j];
            if(memo[i - 1][j - chefs[i - 1]] != -1)
                memo[i][j] = memo[i - 1][j - chefs[i - 1]] + min(chefs[i - 1], n);

            if(j >= sum && memo[i][j] >= k*n){
                najbolje = min(najbolje, j - sum);
            }
        }
    }

    if(najbolje != 99999997)
        cout << najbolje << endl;
    else
        cout << "Impossible" << endl;

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 110712 KB Output is correct
2 Correct 98 ms 110712 KB Output is correct
3 Correct 98 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 99 ms 110724 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 98 ms 110712 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 110712 KB Output is correct
2 Correct 98 ms 110712 KB Output is correct
3 Correct 98 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 99 ms 110724 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 98 ms 110712 KB Output is correct
9 Correct 100 ms 110768 KB Output is correct
10 Correct 100 ms 110688 KB Output is correct
11 Correct 100 ms 110696 KB Output is correct
12 Correct 104 ms 110768 KB Output is correct
13 Incorrect 100 ms 110824 KB Output isn't correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 110768 KB Output is correct
2 Correct 153 ms 110804 KB Output is correct
3 Correct 151 ms 110788 KB Output is correct
4 Correct 147 ms 110808 KB Output is correct
5 Correct 146 ms 110796 KB Output is correct
6 Correct 135 ms 110812 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 110712 KB Output is correct
2 Correct 98 ms 110712 KB Output is correct
3 Correct 98 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 99 ms 110724 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 98 ms 110712 KB Output is correct
9 Correct 100 ms 110768 KB Output is correct
10 Correct 100 ms 110688 KB Output is correct
11 Correct 100 ms 110696 KB Output is correct
12 Correct 104 ms 110768 KB Output is correct
13 Incorrect 100 ms 110824 KB Output isn't correct