Submission #584249

#	Time	Username	Problem	Language	Result	Execution time	Memory
584249		juggernaut	Kitchen (BOI19_kitchen)	C++14	100 / 100	33 ms	696 KiB

kitchen

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int dp[100005];
int a[305];
int n,m,k;
int sum;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]<k)return puts("Impossible"),0;
		sum+=a[i];
	}
	for(int i=1;i<100005;i++)dp[i]=-2e9;
	for(int i=1;i<=m;i++){
		int x;
		scanf("%d",&x);
      	int pivot=min(x,n);
		for(int j=100000;j>=x;j--)umax(dp[j],dp[j-x]+pivot);
	}
	int ans=2e9;
	for(int i=0;i<100005;i++)
	if(dp[i]>=k*n&&i>=sum)umin(ans,i-sum);
	if(ans==(int)2e9)return puts("Impossible"),0;
	cout<<ans;
}

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d%d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
kitchen.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
kitchen.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~

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