Submission #1099291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099291		vjudge1	Kitchen (BOI19_kitchen)	C++17	100 / 100	23 ms	1172 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;

long long a[305], b[305], dp[90005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	long long n, m, k, i, j, check=1;
	cin >> n >> m >> k;
	for (i=1; i<=n; i++) {cin >> a[i]; if (a[i]<k) {check=0;}; a[i]+=a[i-1];};
	dp[0]=0;
	for (i=1; i<=90000; i++) {dp[i]=-1;};
	for (i=1; i<=m; i++)
    {
        cin >> b[i];
        for (j=90000; j>=b[i]; j--)
        {
            if (dp[j-b[i]]!=-1) {dp[j]=max(dp[j], dp[j-b[i]]+min(n, b[i]));};
        };
    };
    for (i=a[n]; i<=90000; i++)
    {
        if (dp[i]>=n*k) {break;};
    };
    if (check==0 || i==90001) {cout << "Impossible";}
    else {cout << i-a[n];};
}

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