oj.uz

Submission #136744

# Submission time Handle Problem Language Result Execution time Memory
136744 2019-07-26T08:05:55 Z azatega Kitchen (BOI19_kitchen) C++11
50 / 100
 153 ms 110840 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] = 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 98 ms 110788 KB Output is correct
2 Correct 97 ms 110668 KB Output is correct
3 Correct 100 ms 110840 KB Output is correct
4 Correct 99 ms 110716 KB Output is correct
5 Correct 98 ms 110712 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 276 KB Output is correct
8 Correct 97 ms 110712 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 110788 KB Output is correct
2 Correct 97 ms 110668 KB Output is correct
3 Correct 100 ms 110840 KB Output is correct
4 Correct 99 ms 110716 KB Output is correct
5 Correct 98 ms 110712 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 276 KB Output is correct
8 Correct 97 ms 110712 KB Output is correct
9 Correct 99 ms 110812 KB Output is correct
10 Correct 103 ms 110712 KB Output is correct
11 Correct 102 ms 110740 KB Output is correct
12 Correct 101 ms 110708 KB Output is correct
13 Incorrect 100 ms 110768 KB Output isn't correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 110688 KB Output is correct
2 Correct 143 ms 110816 KB Output is correct
3 Correct 153 ms 110712 KB Output is correct
4 Correct 152 ms 110828 KB Output is correct
5 Correct 153 ms 110720 KB Output is correct
6 Correct 140 ms 110712 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 110712 KB Output is correct
2 Correct 104 ms 110712 KB Output is correct
3 Correct 106 ms 110712 KB Output is correct
4 Correct 104 ms 110732 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 98 ms 110788 KB Output is correct
2 Correct 97 ms 110668 KB Output is correct
3 Correct 100 ms 110840 KB Output is correct
4 Correct 99 ms 110716 KB Output is correct
5 Correct 98 ms 110712 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 276 KB Output is correct
8 Correct 97 ms 110712 KB Output is correct
9 Correct 99 ms 110812 KB Output is correct
10 Correct 103 ms 110712 KB Output is correct
11 Correct 102 ms 110740 KB Output is correct
12 Correct 101 ms 110708 KB Output is correct
13 Incorrect 100 ms 110768 KB Output isn't correct