Submission #140826

#	Time	Username	Problem	Language	Result	Execution time	Memory
140826		Shelby	Kitchen (BOI19_kitchen)	C++11	100 / 100	42 ms	848 KiB

kitchen

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

int dp[MAXN*MAXN],a[MAXN],b[MAXN],val[MAXN];
bool ok[MAXN*MAXN];

int main()
{ int i,j,n,m,k,sum=0,need=0,mn;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<n;i++)
{
    scanf("%d",&a[i]);

    if(i==0) mn=a[i];
    else mn=min(mn,a[i]);

    sum=sum+a[i];

    need+=k;
}

for(i=0;i<m;i++)
{
    scanf("%d",&b[i]);

    val[i]=min(b[i],n);
}

ok[0]=true;

for(i=0;i<m;i++)
{
    for(j=MAXN*MAXN-1;j>=b[i];j--)
    {
        if(ok[j-b[i]]==true)
        {
            ok[j]=true;

            dp[j]=max(dp[j], dp[j-b[i]]+val[i] );
        }
    }
}

if(mn<k) printf("Impossible\n");
else
{
    for(i=sum;i<MAXN*MAXN;i++)
    {
        if(ok[i]==true && dp[i]>=need)
        {
            printf("%d\n",i-sum);
            return 0;
        }
    }

    printf("Impossible\n");
}

//for(i=0;i<9;i++) cout << dp[i] << " ";

    return 0;
}

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:10:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d%d%d",&n,&m,&k);
 ~~~~~^~~~~~~~~~~~~~~~~~~
kitchen.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&a[i]);
     ~~~~~^~~~~~~~~~~~
kitchen.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&b[i]);
     ~~~~~^~~~~~~~~~~~
kitchen.cpp:45:1: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
 if(mn<k) printf("Impossible\n");
 ^~

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