Submission #887150

#	Time	Username	Problem	Language	Result	Execution time	Memory
887150		BBart888	Bank (IZhO14_bank)	C++17	100 / 100	126 ms	20920 KiB

bank

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"
//#include "dreaming.h"


using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;



const int MAXN = 3e6 + 11; 
using ll = long long;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1000000021;
const ll P = 31;



/*
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
	if ((name.size())) {
		freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
*/



int n, m;
int a[MAXN];
int b[MAXN];
pair<int, ll> dp[MAXN];
int flag;


int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	//setIO("movie");
	
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = 0; i < m; i++)
		cin >> b[i];


	for (int mask = 0; mask < (1 << m); mask++)
	{
		for (int j = 0; j < m; j++)
		{
			pair<int, int> cur = dp[mask ^ (1 << j)];
			if (((1 << j) & mask) == 0)
				continue;
			int C = b[j];

			if (cur.second + C == a[cur.first])
			{
				dp[mask] = max(dp[mask], make_pair(cur.first + 1, 0ll));
			}
			else if(cur.second + C < a[cur.first])
			{
				dp[mask] = max(dp[mask], make_pair(cur.first,(ll)cur.second + C));
			}
		}
	//	for (int j = 0; j < m; j++)
			//if ((1 << j) & mask)
				//cout << 1;
			//else
		//		cout << 0;
		
		//cout << " " << dp[mask].first << " " << dp[mask].second << '\n';
		if (dp[mask].first == n)
			flag = 1;
	}

	cout << (flag ? "YES\n" : "NO\n");





	

	return 0;
}

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