제출 #1333936

#제출 시각아이디문제언어결과실행 시간메모리
1333936hoangtien69Kitchen (BOI19_kitchen)C++20
100 / 100
15 ms580 KiB
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int n, m, k;
int a[305];
int b[305];
int total = 0;
int totalB = 0;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        total += a[i];
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        totalB += b[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] < k)
        {
            cout << "Impossible";
            return 0;
        }
    }
    int maxx = totalB;
    vector<int> dp(maxx + 1, -INF);
    dp[0] = 0;
    for (int i = 1; i <= m; i++)
    {
        int real = min(b[i], n);
        for (int j = maxx; j >= b[i]; j--)
        {
            if (dp[j - b[i]] != -INF)
            {
                dp[j] = max(dp[j], dp[j - b[i]] + real);
            }
        }
    }
    int ans = -1;
    for (int i = total; i <= maxx; i++)
    {
        if (dp[i] >= n * k)
        {
            ans = i - total;
            break;
        }
    }
    if (ans == -1)
    {
        cout << "Impossible";
    }
    else
    {
        cout << ans;
    }
}
#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...