Submission #926090

#	Time	Username	Problem	Language	Result	Execution time	Memory
926090		vjudge1	Kitchen (BOI19_kitchen)	C++17	100 / 100	28 ms	23456 KiB

kitchen

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
typedef long long ll;

const ll mod=1e9+7;
const ll inf=mod;
const int N=5e6+4;

int n,m,k,a[N],b[N];
int dp[N];

void solve(){
	cin>>n>>m>>k;
	int sum=0;
	for(int i=0; i<N; ++i) dp[i]=-mod;
	for(int i=1; i<=n; ++i){
		cin>>a[i];
		sum+=a[i];
		if(a[i]<k){
			cout<<"Impossible\n";
			return;
		}
	}
	for(int i=1; i<=m; ++i){
		cin>>b[i];
	}
	dp[0]=0;
	for(int i=1; i<=m; ++i){
		for(int j=90002; j>=b[i]; --j){
			dp[j]=max(dp[j-b[i]]+min(b[i],n),dp[j]);
		}
	}
	int ans=mod;
	for(int i=sum; i<=90002; ++i){
		if(dp[i]>=n*k){
			cout<<i-sum<<endl;
			return;
		}
	}
	cout<<"Impossible\n";
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tt=1;
//	cin>>tt;
	while(tt--) {
		solve();
	}
}

Compilation message (stderr)

kitchen.cpp: In function 'void solve()':
kitchen.cpp:39:6: warning: unused variable 'ans' [-Wunused-variable]
   39 |  int ans=mod;
      |      ^~~

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