Submission #566746

#	Time	Username	Problem	Language	Result	Execution time	Memory
566746		milisav	Kitchen (BOI19_kitchen)	C++14	100 / 100	28 ms	676 KiB

kitchen

#include<bits/stdc++.h>
#define maxn 305
using namespace std;
int n,m,k;
int a[maxn];
int b[maxn];
int dp[maxn*maxn];
int main() {
    scanf("%d %d %d",&n,&m,&k);
    int sm=0;
    int mn=1e9;
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        sm+=a[i];
        mn=min(mn,a[i]);
    }
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    if(mn<k) {
        printf("Impossible");
        return 0;
    }
    for(int i=1;i<maxn*maxn;i++) dp[i]=-1e9;
    for(int i=1;i<=m;i++) {
        int val=min(n,b[i]);
        for(int j=maxn*maxn-1;j>=b[i];j--) {
            dp[j]=max(dp[j],dp[j-b[i]]+val);
        }
    }
    int ans=-1;
    for(int i=sm;i<maxn*maxn;i++) {
        if(dp[i]>=n*k) {
            ans=i;
            break;
        }
    }
    if(ans==-1) printf("Impossible");
    else printf("%d",ans-sm);
    return 0;
}

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d %d %d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
kitchen.cpp:17:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     for(int i=1;i<=m;i++) scanf("%d",&b[i]);
      |                           ~~~~~^~~~~~~~~~~~

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