Submission #566158

#	Time	Username	Problem	Language	Result	Execution time	Memory
566158		racsosabe	Bank (IZhO14_bank)	C++14	19 / 100	434 ms	26752 KiB

bank

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

const int N = 20 + 5;
const int MASK = 1 << 20;

int n;
int m;
int neg;
int a[N];
int b[N];
int sum[MASK];
bool vis[MASK];
int nxt[2][MASK];
int memo[2][MASK];

void preprocess(){
	while(neg < n and a[neg] < 0) neg++;
	for(int mask = 1; mask < (1 << m); mask++){
		sum[mask] = sum[mask & (mask - 1)] + b[__builtin_ctz(mask)];
		int lo = 0, hi = neg;
		while(lo < hi){
			int mi = lo + (hi - lo) / 2;
			if(a[mi] < sum[mask]) hi = mi;
			else lo = mi + 1;
		}
		nxt[0][mask] = a[lo];
		lo = neg, hi = n;
		while(lo < hi){
			int mi = lo + (hi - lo) / 2;
			if(sum[mask] <= a[mi]) lo = mi + 1;
			else hi = mi;
		}
		nxt[1][mask] = a[lo];
	}
}

vector<int> get_order(){
	queue<int> Q;
	Q.emplace(0);
	vector<int> res;
	while(!Q.empty()){
		int mask = Q.front(); Q.pop();
		res.emplace_back(mask);
		for(int i = 0, p = 1; i < m; i++, p <<= 1){
			if(mask & p) continue;
			if(vis[mask | p]) continue;
			Q.emplace(mask | p);
			vis[mask | p] = true;
		}
	}
	return res;
}

bool solve(){
	vector<int> order = get_order();
	for(int mask = 0, l = 1 << m; mask < l; mask++) vis[mask] = false;
	for(int at = 0; at + 1 < order.size(); at++){
		int mask = order[at];
		for(int i = 0, p = 1; i < m; i++, p <<= 1){
			if(mask & p) continue;
			int new_sum = sum[mask | p];
			int val = memo[0][mask];
			if(new_sum == nxt[0][sum[mask]]) val += 1;
			memo[0][mask | p] = max(memo[0][mask | p], val);
		}
	}
	for(int at = 0; at < order.size(); at++){
		int mask = order[at];
		for(int i = 0, p = 1; i < m; i++, p <<= 1){
			if(mask & p) continue;
			int new_sum = sum[mask | p];
			int val = memo[0][mask];
			if(new_sum == nxt[1][sum[mask]]) val += 1;
			memo[1][mask | p] = max(memo[1][mask | p], val);
		}
	}
	for(int at = 0; at + 1 < order.size(); at++){
		int mask = order[at];
		for(int i = 0, p = 1; i < m; i++, p <<= 1){
			if(mask & p) continue;
			int new_sum = sum[mask | p];
			int val = memo[1][mask];
			if(new_sum == nxt[1][sum[mask]]) val += 1;
			memo[1][mask | p] = max(memo[1][mask | p], val);
		}
	}
	for(int mask = 0, l = 1 << m; mask < l; mask++){
		if(memo[0][mask] == n) return true;
		if(memo[1][mask] == n) return true;
	}
	return false;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++) scanf("%d", a + i);
	for(int i = 0; i < m; i++) scanf("%d", b + i);
	sort(a, a + n);
	for(int i = 1; i < n; i++) a[i] += a[i - 1];
	preprocess();
	puts(solve() ? "YES" : "NO");
	return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool solve()':
bank.cpp:58:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int at = 0; at + 1 < order.size(); at++){
      |                  ~~~~~~~^~~~~~~~~~~~~~
bank.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int at = 0; at < order.size(); at++){
      |                  ~~~^~~~~~~~~~~~~~
bank.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int at = 0; at + 1 < order.size(); at++){
      |                  ~~~~~~~^~~~~~~~~~~~~~
bank.cpp: In function 'int main()':
bank.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:97:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  for(int i = 0; i < n; i++) scanf("%d", a + i);
      |                             ~~~~~^~~~~~~~~~~~~
bank.cpp:98:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |  for(int i = 0; i < m; i++) scanf("%d", b + i);
      |                             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29