Submission #731724

#	Time	Username	Problem	Language	Result	Execution time	Memory
731724		Juan	Bank (IZhO14_bank)	C++17	25 / 100	1083 ms	444 KiB

bank

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(03)
// #define int long long
#define pii pair<int, int>
#define ff first
#define ss second
const int maxn = 22;

int sal[maxn], notes[maxn];
bool dp[maxn][1<<(maxn-1)];

int32_t main(){
	ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> sal[i];
	for(int i = 0; i < m; i++) cin >> notes[i];

	dp[0][0] = true;

	for(int i = 1; i <= n; i++){

		// p cada mask de notas
		for(int mask = 0; mask < (1<<m); mask++){
			vector<int> aux;
			for(int e = 0; e < m; e++) if(mask & (1<<e)) aux.push_back(e);

			// checar, entre as submasks, quais formam salario valido
			// p sal[i] e se a submask restante eh valida p anterior
			for(int submask = 0; submask < (1<<aux.size()); submask++){
				int submask_val=0, val=0;
				for(int e = 0; e < aux.size(); e++) if(submask & (1<<e)) val+=notes[aux[e]], submask_val += (1<<(aux[e]));
				if(val==sal[i] && dp[i-1][mask^submask_val]) dp[i][mask] = true;
			}
		}
	}

	bool found = false;
	for(int i = 0; i < (1<<m); i++) if(dp[n][i]) {cout << "YES\n"; found = true; break;}
	if(found==false) cout << "NO\n";
}

Compilation message (stderr)

bank.cpp: In function 'int32_t main()':
bank.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int e = 0; e < aux.size(); e++) if(submask & (1<<e)) val+=notes[aux[e]], submask_val += (1<<(aux[e]));
      |                    ~~^~~~~~~~~~~~

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