| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 843772 | Firas_Briki | 은행 (IZhO14_bank) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define dbg(...)
#endif
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb(n) push_back(n)
#define F first
#define S second
#define mp(x, y) make_pair(x, y)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define nop cout << -1 << endl;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
const ll sup = 1e18;
const ll inf = -1e18;
const ll mod = 1e9 + 7;
const int N_Max = 2e4 + 7;
const int Nax = 15;
const int LOG = 18;
const int BITS = 30;
const int ALPHA = 26;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}
vector<int> s[N_Max];
int dp[25][(1 << 21)];
int a[25], b[25];
int N, M;
int work(int i, int mask){
if (i >= N) return 1;
int &ret = dp[i][mask];
if (ret != -1) return ret;
ret = 0;
for (int curr : s[a[i]])
if (!(mask & curr)) ret |= work(i + 1, mask | curr);
return ret;
}
void solve(){
cin >> N >> M;
memset(dp, -1, sizeof(dp));
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++){
int sum = 0;
for (int i = 0; i < M; i++)
if (mask & (1 << i)) sum += b[i];
s[sum].pb(mask);
}
int ans = work(0, 0);
if (ans) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main(){
FAST
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}