Submission #139925

#	Time	Username	Problem	Language	Result	Execution time	Memory
139925		ae04071	Kitchen (BOI19_kitchen)	C++11	100 / 100	29 ms	760 KiB

kitchen

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

const int INF = 1e8;

int n,m,K,a[300],b[300];
int dp[90001];

int main() {
    scanf("%d%d%d",&n,&m,&K);
    for(int i=0;i<n;i++) scanf("%d",a+i);
    for(int i=0;i<m;i++) scanf("%d",b+i);

    int as=0;
    for(int i=0;i<n;i++) {
        if(a[i]<K) {
            puts("Impossible");
            return 0;
        }as+=a[i];
    }

    for(int i=1;i<=90000;i++) dp[i] = -INF;
    for(int i=0;i<m;i++) {
        for(int j=90000-b[i];j>=0;j--) dp[j+b[i]] = max(dp[j+b[i]], dp[j] + min(n,b[i]));
    }
    
    for(int i=as;i<=90000;i++) if(dp[i] >= n*K) {
        printf("%d\n",i - as);
        return 0;
    }
    puts("Impossible");
    
    return 0;
}

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:10:10: 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:11:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<n;i++) scanf("%d",a+i);
                          ~~~~~^~~~~~~~~~
kitchen.cpp:12:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;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