Submission #41207

#	Time	Username	Problem	Language	Result	Execution time	Memory
41207		wzy	Bank (IZhO14_bank)	C++14	100 / 100	625 ms	31104 KiB

bank

#include <bits/stdc++.h>
using namespace std;
int n  , m , v[21] , b[21];
bool dp[21][1<<21];
vector<int> submask[1010];
bool vis[21][1<<21];

bool solve(int i ,int j){
	if(i == n) return 1;
	if(vis[i][j]) return dp[i][j];
	vis[i][j] = true;
	int vv = v[i];
	for(int w = 0 ; w < submask[v[i]].size() ; w++){
		int v = submask[vv][w];
		if(v&j) continue;
		dp[i][j] |= solve(i + 1 , j | v);
	}
	return dp[i][j];
}

int main(){
	scanf("%d%d" , &n , &m);
	int maxv = 0;
	for(int i = 0 ; i < n;i++){
		scanf("%d" , & v[i]);
		maxv = max(maxv , v[i]);
	}
	for(int i = 0 ; i < m ; i++) {
		scanf("%d" , & b[i]);
	}
	for(int j = 0 ; j < (1<<m) ; j++){
		int sumj = 0;
		for(int w = 0 ; w < m ; w++){
			if(1<<w & j) sumj +=  b[w];
		}
		if(sumj == 0 || sumj > maxv) continue;
		submask[sumj].push_back(j);
	}
	int q = solve(0 , 0);
	q ? puts("YES") : puts("NO");
}	

Compilation message (stderr)

bank.cpp: In function 'bool solve(int, int)':
bank.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int w = 0 ; w < submask[v[i]].size() ; w++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~
bank.cpp: In function 'int main()':
bank.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n , &m);
  ~~~~~^~~~~~~~~~~~~~~~~~
bank.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , & v[i]);
   ~~~~~^~~~~~~~~~~~~~~
bank.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , & b[i]);
   ~~~~~^~~~~~~~~~~~~~~

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