oj.uz

Submission #765453

# Submission time Handle Problem Language Result Execution time Memory
765453 2023-06-24T13:42:04 Z vjudge1 Bank (IZhO14_bank) C++17
0 / 100
 1 ms 340 KB 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <bitset>
#include <deque>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 20;
pair<int, int> f[1 << maxn];
int a[maxn], b[maxn];
int main() {
	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];
	}
	sort(a + 1, a + n + 1, greater<int>());
	sort(b + 1, b + m + 1);
	f[0] = make_pair(0, 0);
	for (int s = 1; s < (1 << m); s++) {
		f[s] = make_pair(0, inf);
		for (int i = 0; i < m; i++) {
			if (~s & (1 << i)) continue;
			pair<int, int> pre = f[s ^ (1 << i)];
			if (pre.first == n) break;
			if (pre.second + b[i] == a[pre.first]) {
				pre.first++;
				pre.second = 0;
			} else if (pre.second + b[i] < a[pre.first]) {
				pre.second += b[i];
			} else {
				break;
			}
			f[s] = max(f[s], pre);
		}
	}
	for (int s = 0; s < (1 << m); s++) {
		if (f[s].first == n) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -