oj.uz

Submission #136741

# Submission time Handle Problem Language Result Execution time Memory
136741 2019-07-26T08:03:59 Z azatega Kitchen (BOI19_kitchen) C++11
29 / 100
 148 ms 110968 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 97 ms 110712 KB Output is correct
2 Correct 97 ms 110844 KB Output is correct
3 Correct 97 ms 110712 KB Output is correct
4 Correct 98 ms 110672 KB Output is correct
5 Correct 99 ms 110712 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 98 ms 110708 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 97 ms 110844 KB Output is correct
3 Correct 97 ms 110712 KB Output is correct
4 Correct 98 ms 110672 KB Output is correct
5 Correct 99 ms 110712 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 98 ms 110708 KB Output is correct
9 Correct 99 ms 110728 KB Output is correct
10 Correct 99 ms 110676 KB Output is correct
11 Correct 100 ms 110712 KB Output is correct
12 Correct 99 ms 110708 KB Output is correct
13 Incorrect 103 ms 110716 KB Output isn't correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 110856 KB Output is correct
2 Correct 141 ms 110704 KB Output is correct
3 Correct 148 ms 110712 KB Output is correct
4 Correct 147 ms 110840 KB Output is correct
5 Correct 146 ms 110968 KB Output is correct
6 Correct 136 ms 110768 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 110712 KB Output is correct
2 Correct 97 ms 110844 KB Output is correct
3 Correct 97 ms 110712 KB Output is correct
4 Correct 98 ms 110672 KB Output is correct
5 Correct 99 ms 110712 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 98 ms 110708 KB Output is correct
9 Correct 99 ms 110728 KB Output is correct
10 Correct 99 ms 110676 KB Output is correct
11 Correct 100 ms 110712 KB Output is correct
12 Correct 99 ms 110708 KB Output is correct
13 Incorrect 103 ms 110716 KB Output isn't correct