이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
This code belongs to Aadit Ambadkar
Date: 2022-01-25 21:41:41
Problem: bank
*/
#include <bits/stdc++.h>
using namespace::std;
typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define FF first
#define SS second
vector<int> a;
vector<int> b;
int n, m;
bool works = false;
vector<vector<bool>> vis(21, vector<bool>(1048576, false));
void recur(int ly, int cmsk) {
vis[ly][cmsk]=true;
int sm = 0;
F0R(i, m) {
if (!(cmsk & (1 << i))) sm+=b[i];
}
if (sm < a[ly]) {
return;
}
for (int msk = cmsk+1; msk < (1<<m); msk++) {
if ((cmsk & msk) == cmsk) { // learned by thinking
int tmsk = msk ^ cmsk;
int sum = 0;
F0R(i, m) {
if (tmsk & (1<<i)) {
sum+=b[i];
}
if (sum > a[ly]) break;
}
if (sum==a[ly]) {
if (ly == n-1) {
cout << "YES\n";
exit(EXIT_SUCCESS);
} else {
if (!vis[ly+1][msk]) {
recur(ly+1, msk);
}
}
}
}
}
}
int main() {
fastio;
cin >> n >> m;
if (n==1) {
int k; cin >> k;
vector<int> arr(m, 0);
F0R(i, m) cin >> arr[i];
sort(arr.begin(), arr.end());
set<int> psbl;
psbl.insert(0);
F0R(i, m)
for (auto it = psbl.rbegin(); it != psbl.rend(); it++) {
psbl.insert((*it)+arr[i]);
}
if (psbl.count(k)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
} else {
int x;
F0R(i, n) {
cin >> x;
a.pb(x);
}
F0R(i, m) {
cin >> x;
b.pb(x);
}
recur(0, 0);
cout << "NO\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |