oj.uz

Submission #136759

# Submission time Handle Problem Language Result Execution time Memory
136759 2019-07-26T08:19:20 Z azatega Kitchen (BOI19_kitchen) C++11
50 / 100
 146 ms 110884 KB 
#include <iostream>

using namespace std;

int cost[310];
int chefs[310];
int memo[310][91000];
int n, m, k, sum = 0, sum_of_chefs = 0;

int main()
{
    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];
        sum_of_chefs += chefs[i];
    }

    if(sum_of_chefs < sum || m < k){
        cout << "Impossible" << endl;
        return 0;
    }

    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 <= sum_of_chefs; 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] = max(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 97 ms 110712 KB Output is correct
2 Correct 101 ms 110732 KB Output is correct
3 Correct 95 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 95 ms 110684 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 110712 KB Output is correct
2 Correct 101 ms 110732 KB Output is correct
3 Correct 95 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 95 ms 110684 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 96 ms 110756 KB Output is correct
10 Correct 95 ms 110684 KB Output is correct
11 Correct 95 ms 110712 KB Output is correct
12 Correct 95 ms 110712 KB Output is correct
13 Incorrect 97 ms 110656 KB Output isn't correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 110840 KB Output is correct
2 Correct 122 ms 110872 KB Output is correct
3 Correct 124 ms 110884 KB Output is correct
4 Correct 146 ms 110744 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 137 ms 110712 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 110712 KB Output is correct
2 Correct 96 ms 110696 KB Output is correct
3 Correct 96 ms 110712 KB Output is correct
4 Correct 95 ms 110712 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 110712 KB Output is correct
2 Correct 101 ms 110732 KB Output is correct
3 Correct 95 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 95 ms 110684 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 96 ms 110756 KB Output is correct
10 Correct 95 ms 110684 KB Output is correct
11 Correct 95 ms 110712 KB Output is correct
12 Correct 95 ms 110712 KB Output is correct
13 Incorrect 97 ms 110656 KB Output isn't correct