Submission #928912

#	Time	Username	Problem	Language	Result	Execution time	Memory
928912		Faisal_Saqib	Kitchen (BOI19_kitchen)	C++17	100 / 100	22 ms	1372 KiB

kitchen

#include <iostream>
using namespace std;
#define int long long
const int N=301;
int a[N],b[N],c[N];
int dp[N*N+N+N];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n,m,k;
    cin>>n>>m>>k;
    int s1=0;
    int s2=n*k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]<k)
        {
            cout<<"Impossible\n";
            exit(0);
        }
        s1+=a[i];
    }
    int mx=301*301;
    for(int j=0;j<=mx;j++)
        dp[j]=-1e9;
    dp[0]=0;
    int ans=-1;
    for(int j=0;j<m;j++)
    {
        cin>>b[j];
        c[j]=min(n,b[j]);
    }
    for(int j=0;j<m;j++)
    {
        for(int s3=mx-b[j];s3>=0;s3--)
        {
            dp[s3+b[j]]=max(dp[s3+b[j]],dp[s3]+c[j]);
        }
    }
    for(int s3=s1;s3<=mx;s3++)
        if(dp[s3]>=s2)
        {
            cout<<s3-s1<<'\n';
            return 0;
        }
    cout<<"Impossible\n";
}

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:30:9: warning: unused variable 'ans' [-Wunused-variable]
   30 |     int ans=-1;
      |         ^~~

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