Submission #382559

#	Time	Username	Problem	Language	Result	Execution time	Memory
382559		mariowong	Bank (IZhO14_bank)	C++14	100 / 100	520 ms	21288 KiB

bank

#include <bits/stdc++.h>
using namespace std;
 
int m,n,a[25],b[25],val[1100000];
vector <int> v,ps[25],v2;
bool dp[25][1100000];
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i=1;i<=n;i++){
		cin >> a[i];
	}
	for (int i=0;i<m;i++){
		cin >> b[i];
	}
	for (int i=0;i<(1<<m);i++){
		for (int j=0;j<m;j++){
			if ((i&(1<<j)) > 0)
			val[i]+=b[j];
		}
		for (int j=1;j<=n;j++){
			if (val[i] == a[j])
			ps[j].push_back(i);
		}
	}
	v.push_back(0);
	for (int i=1;i<=n;i++){
		v2.clear();
		for (int j=0;j<ps[i].size();j++){
			for (int k=0;k<v.size();k++){
				if ((v[k]&ps[i][j]) == 0 && !dp[i][v[k]+ps[i][j]]){
					v2.push_back(v[k]+ps[i][j]);
					dp[i][v[k]+ps[i][j]]=true;
				}
			}
		}
		v.clear(); v=v2;
		if ((int)v.size() == 0){
			cout << "NO\n";
			return 0;
		}
	}
	cout << "YES\n";
	return 0;
}	

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int j=0;j<ps[i].size();j++){
      |                ~^~~~~~~~~~~~~
bank.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for (int k=0;k<v.size();k++){
      |                 ~^~~~~~~~~

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