Submission #398697

#	Time	Username	Problem	Language	Result	Execution time	Memory
398697		iulia13	Kitchen (BOI19_kitchen)	C++14	100 / 100	28 ms	972 KiB

kitchen

#include <iostream>
#include <algorithm>
using namespace std;
const int nmax = 305;
int dp[2][nmax * nmax];
int b[nmax];
int main()
{
    ///bagi artificial o singura data un chef la o anumita mancarica ca te int doar ca suma timp chefi >= suma timpi mancare dupa
    ///=> un chef contribuie la min(n, bi) mancarici
    ///tb n*k in total minim
    ///dp[x] = x ore chefi ; contributie artificiala
    ///dp[i][x] -> primii i chefi x ore => dp[i+1][x] = dp[i][x] (nu te int) + dp[i][x - b[i + 1]] => 0/1 dp
    int A, a, n, m, k, i, j, B;
    cin >> n >> m >> k;
    A = B = 0;
    for (i = 1; i <= n; i++)
    {
        cin >> a; A += a;
        if (a < k)
        {
            cout << "Impossible";
            return 0;
        }
    }
    for (j = 1; j <= m; j++)
        cin >> b[j], B += b[j];
    for (i = 0; i <= 1; i++)
        for (j = 0; j <= B; j++)
            dp[i][j] = -2e9;
    dp[0][0] = 0;
    dp[1][0] = 0;
    sort(b + 1, b + m + 1);
    reverse(b + 1, b + m + 1);
    for (i = 1; i <= m; i++)
        for (j = b[i]; j <= B; j++)
            dp[i % 2][j] = max(dp[1 - i % 2][j - b[i]] + min(b[i], n), dp[1 - i % 2][j]);
    for (i = A; i <= B; i++)
        if (dp[m % 2][i] >= n * k)
        {
            cout << i - A;
            return 0;
        }
    cout << "Impossible";
    return 0;
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28