제출 #398697

#제출 시각아이디문제언어결과실행 시간메모리
398697iulia13Kitchen (BOI19_kitchen)C++14
100 / 100
28 ms972 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...