oj.uz

Submission #136758

# Submission time Handle Problem Language Result Execution time Memory
136758 2019-07-26T08:16:31 Z azatega Kitchen (BOI19_kitchen) C++11
50 / 100
 144 ms 110856 KB 
#include <iostream>

using namespace std;

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



int main()
{
    int n, m, k, sum = 0, sum_of_chefs = 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];
        sum_of_chefs += chefs[i];
    }

    if(sum_of_chefs < sum){
        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 96 ms 110660 KB Output is correct
2 Correct 97 ms 110712 KB Output is correct
3 Correct 97 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 95 ms 110712 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 96 ms 110660 KB Output is correct
2 Correct 97 ms 110712 KB Output is correct
3 Correct 97 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 95 ms 110712 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 97 ms 110712 KB Output is correct
10 Correct 97 ms 110720 KB Output is correct
11 Correct 96 ms 110712 KB Output is correct
12 Correct 96 ms 110712 KB Output is correct
13 Incorrect 97 ms 110752 KB Output isn't correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 110848 KB Output is correct
2 Correct 123 ms 110768 KB Output is correct
3 Correct 125 ms 110712 KB Output is correct
4 Correct 144 ms 110856 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 126 ms 110824 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 110684 KB Output is correct
2 Correct 97 ms 110768 KB Output is correct
3 Correct 96 ms 110712 KB Output is correct
4 Correct 96 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 96 ms 110660 KB Output is correct
2 Correct 97 ms 110712 KB Output is correct
3 Correct 97 ms 110712 KB Output is correct
4 Correct 97 ms 110712 KB Output is correct
5 Correct 95 ms 110712 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 97 ms 110712 KB Output is correct
10 Correct 97 ms 110720 KB Output is correct
11 Correct 96 ms 110712 KB Output is correct
12 Correct 96 ms 110712 KB Output is correct
13 Incorrect 97 ms 110752 KB Output isn't correct