Submission #1103637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103637		vjudge1	Bank (IZhO14_bank)	C++14	100 / 100	358 ms	4736 KiB

bank

#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define IOS      ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F        first
#define S        second
#define sz(x)    x.size()
#define all(x)   x.begin(), x.end()
#define pb       push_back

const int Inf    = 2e9 + 10;
const int Mod    = 1e9 + 7;
const int LG     = 25;
const int SQ     = 400;
const int Alpha  = 27;
const int maxN   = 25;
const int maxL   = 2e6;
const int maxS   = 4e4 + 10;

int a[maxN];
int b[maxN];
int ps[maxN];
int two[maxN];
int dp[maxL];

vector <int> ConvertBinary(int x) {
	vector <int> ret;
	while(x) {
		ret.pb(x%2);
		x/=2;
	}
	return ret;
}

int main() {
	IOS;
	
	two[0] = 1;
	for(int i = 1; i < maxN; i++)
		two[i] = 2*two[i-1];

	int n, m;
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= m; i++)
		cin >> b[i];

	ps[1] = a[1];
	for(int i = 2; i <= n; i++)
		ps[i] = ps[i-1] + a[i];

	for(int i = 0; i < (1 << m); i++) {
		int mx = 0;
		int sum = 0;

		vector <int> bin = ConvertBinary(i);
		for(int j = 0; j < sz(bin); j++) {
			if(bin[j] == 1) {
				sum += b[j+1];
				mx = max(mx, dp[i-two[j]]);
			}
		}

		if(sum == ps[mx+1])
			mx++;

		dp[i] = mx;
	}

	if(dp[(1<<m)-1] == n)
		cout << "YES\n";
	else
		cout << "NO\n";
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for(int j = 0; j < sz(bin); j++) {
      |                    ^

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