Submission #1154411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154411		shadow_sami	Kitchen (BOI19_kitchen)	C++20	100 / 100	127 ms	215336 KiB

kitchen

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define fip(a,b) for(int i = a; i<b; i++)
#define fjp(a,b) for(int j = a; j<b; j++)
#define fp(k,a,b) for(int k = a; k<b; k++)
#define fin(a,b) for(int i = a; i>=b; i--)
#define fjn(a,b) for(int j = a; j>=b; j--)
#define fn(k,a,b) for(int k = a; k>=b; k--)
#define fx(a) for(auto x: a)
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define test ll t;cin>>t;while(t--)
#define nli "\n"

void _printn(int x){cerr<<x;}
void _printn(ll x){cerr<<x;}
void _printn(float x){cerr<<x;}
void _printn(double x){cerr<<x;}
void _printn(string x){cerr<<x;}
void _printn(char x){cerr<<x;}
void _printn(bool x){cerr<<x;}
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(vector<T> vv){cerr<<"[ ";fx(vv){ _printn(x);cerr<<", ";}cerr<<"] "<<nli;}

#ifdef SAMI
	#define debug(x) cerr<<#x;cerr<<" ";_printn(x);cerr<<nli;
	#define debg() cerr<<nli;
#else
	#define debug(x)
	#define debg() 
#endif

ll n,m,res,cnt,sum,ans,tptp,tp,tp2;
bool f = 0;
const ll mx = 300 + 5 ;
const ll mod = 1e9 + 7;
ll a[mx];
ll b[mx];
ll dp[mx][90000+10];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	#ifdef SAMI
		freopen("input1.txt","r",stdin);
		freopen("output1.txt","w",stdout);
	#endif

		cin>>n>>m>>tp;
		f = 1;
		res = sum = 0;
		fip(0,mx)
			fjp(0,90000+10)
				dp[i][j] = -1e18;
		fip(1,n+1){
			cin>>a[i];
			if(a[i]<tp)
				f = 0;
			res += a[i];
		}
		if(!f){
			cout<<"Impossible"<<nli;
			return 0;
		}
		fip(1,m+1){
			cin>>b[i];
			sum += b[i];
		}
		dp[0][0] = 0;
		fip(1,m+1){
			fjp(0,sum+1){
				dp[i][j] = max(dp[i-1][j],dp[i][j]);
				if(j-b[i]>=0)
					dp[i][j] = max(dp[i][j],dp[i-1][j-b[i]] + min(n,b[i]));
				// debug(i);
				// debug(j);
				// debug(dp[i][j]);
				// debg();
			}
		}
		ans = 1e18;
		fjp(1,sum+1)
			if(dp[m][j]>=tp*n && j >= res){
				debug(j);
				ans = min(j-res,ans);
			}
		if(ans<1e18)
			cout<<ans<<nli;
		else
			cout<<"Impossible"<<nli;


	cerr<<"time elapsed : "<<setprecision(6)<<clock()*1000.0/CLOCKS_PER_SEC<<nli;
	return 0;
}

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