Submission #1254289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254289		_rain_	Kitchen (BOI19_kitchen)	C++20	20 / 100	1096 ms	106820 KiB

kitchen

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

#define BIT(mask,x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))

template<class X,class Y>
	bool maximize(X &x, Y y){
		if (x<y) return x=y,true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x,Y y){
		if (x>y) return x=y,true; else return false;
	}
	
const string no_wa = "Impossible";
const int inf = (int)1e9+7;
const int N = (int)300;
	int a[N+2] = {} , b[N+2] = {};
	int n , m , k;

namespace subtask1{
	bool check(void){
		return k == 1;
	}
	
	const int MAXSUM = 300 * 300;
		int dp[N+2][MAXSUM+2];
	
	void main_code(){
		int sum = 0;
		for(int i = 1; i <= m; ++i) sum += b[i];
		memset(dp,0,sizeof dp);
		dp[0][0] = 1;
		for(int i = 1; i <= m; ++i) {
			for(int cur_sum = 0; cur_sum <= sum ; ++cur_sum) {
				dp[i][cur_sum] = dp[i-1][cur_sum];
			}
			for(int cur_sum = 0; cur_sum + b[i] <= sum; ++cur_sum){
				maximize(dp[i][cur_sum + b[i]] , dp[i-1][cur_sum]);
			}
		}
		int need_sum = 0;
		for(int i = 1; i <= n; ++i) need_sum += a[i];
		for(int cur_sum = need_sum; cur_sum <= sum ;++cur_sum){
			if (dp[m][cur_sum]){
				cout << cur_sum - need_sum << '\n';
				return ;
			}
		}
		cout<<no_wa<<'\n';
	}
}

namespace subtask2{
	bool check(void){
		return m <= 15;
	}
	
	int need_sum = 0;
	int f[N+2] = {};
	int ans = inf;
	
	void process(vector<int>&data){
		for(int i = 1; i <= n; ++i) f[i] = 0;
		int sum = 0;
		for(auto&x : data) {
			if (b[x] > n) f[1]++;
			else {
				f[1]++ , f[b[x]+1]--;
			}
			sum += b[x];
		}
		if (sum < need_sum) return ;
		for(int i = 1; i <= n; ++i) {
			f[i] += f[i-1];
			if (f[i] < k) return ;
		}
		minimize(ans , sum - need_sum);
	}
	
	void main_code(void){
		for(int i = 1; i <= n; ++i) need_sum += a[i];
		for(int mask = 0; mask < MASK(m); ++mask){
			vector<int>subset;
			for(int i = 0; i < m; ++i) if (BIT(mask,i)) subset.push_back(i+1);
			process(subset);
		}
		if (ans==inf) return void(cout << no_wa);
		cout<<ans;
		return;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define task "main"
	if (fopen(task".inp","r")){
		freopen(task".inp","r",stdin);
		freopen(task".out","w",stdout);
	}
	
	cin >> n >> m >> k;
		if (k > m){
			cout<<no_wa;
			return 0;
		}
	
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1 ; i <= m; ++i) cin >> b[i];
		if (subtask1::check()) return subtask1::main_code() , 0;
		return subtask2::main_code() , 0;
	return 0;
}

Compilation message (stderr)

kitchen.cpp: In function 'int main()':
kitchen.cpp:101:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
kitchen.cpp:102:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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