oj.uz

Submission #136756

# Submission time Handle Problem Language Result Execution time Memory
136756 2019-07-26T08:14:50 Z azatega Kitchen (BOI19_kitchen) C++11
50 / 100
 151 ms 110848 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 < 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 96 ms 110760 KB Output is correct
2 Correct 95 ms 110776 KB Output is correct
3 Correct 96 ms 110700 KB Output is correct
4 Correct 96 ms 110656 KB Output is correct
5 Correct 119 ms 110744 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 110760 KB Output is correct
2 Correct 95 ms 110776 KB Output is correct
3 Correct 96 ms 110700 KB Output is correct
4 Correct 96 ms 110656 KB Output is correct
5 Correct 119 ms 110744 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 107 ms 110724 KB Output is correct
10 Correct 100 ms 110712 KB Output is correct
11 Correct 98 ms 110712 KB Output is correct
12 Correct 99 ms 110748 KB Output is correct
13 Incorrect 98 ms 110808 KB Output isn't correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 110772 KB Output is correct
2 Correct 138 ms 110772 KB Output is correct
3 Correct 146 ms 110768 KB Output is correct
4 Correct 151 ms 110712 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 135 ms 110764 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 110692 KB Output is correct
2 Correct 101 ms 110848 KB Output is correct
3 Correct 102 ms 110712 KB Output is correct
4 Correct 101 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 110760 KB Output is correct
2 Correct 95 ms 110776 KB Output is correct
3 Correct 96 ms 110700 KB Output is correct
4 Correct 96 ms 110656 KB Output is correct
5 Correct 119 ms 110744 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 107 ms 110724 KB Output is correct
10 Correct 100 ms 110712 KB Output is correct
11 Correct 98 ms 110712 KB Output is correct
12 Correct 99 ms 110748 KB Output is correct
13 Incorrect 98 ms 110808 KB Output isn't correct