Submission #166973

#	Time	Username	Problem	Language	Result	Execution time	Memory
166973		Lightning	Bank (IZhO14_bank)	C++14	44 / 100	37 ms	412 KiB

bank

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 30;
const int INF = 1e9;

int n, m, a[N], b[N];

void rec(int pos, int sum) {
	if(pos == m + 1) {
		if(sum == a[1]) {
			cout << "YES\n";
			exit(0);
		}
		return;
	}
	rec(pos + 1, sum + b[pos]);
	rec(pos + 1, sum);
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	fo(i, 1, n, 1) {
		cin >> a[i];
	}
	fo(i, 1, m, 1) {
		cin >> b[i];
	}
	if(m > 10) {
		rec(1, 0);
		cout << "NO\n";
		return 0;
	}
	sort(b + 1, b + m + 1);
	do {
		int sum = 0, j = 1;
		bool ok = 1;
		fo(i, 1, m, 1) {
			sum += b[i];
			if(sum > a[j]) {
				ok = 0;
				break;
			}
			if(sum == a[j]) {
				++j;
				sum = 0;
				if(j > n) break;
			}
		}	
		if(ok && sum == 0 && j == n + 1) {
			cout << "YES\n";
			return 0;
		}
	} while(next_permutation(b + 1, b + m + 1));
	cout << "NO\n";
	return 0;
}

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