제출 #1062065

#제출 시각아이디문제언어결과실행 시간메모리
1062065horezushol은행 (IZhO14_bank)C++14
19 / 100
68 ms12884 KiB
#include<bits/stdc++.h> #define F first #define S second #define SZ(x) ll((x).size()) const char nl = '\n'; using ll = long long; using namespace std; const ll N = 20; const ll NA = 1010; ll sum[(1ll << N)]; vector<ll> v[NA]; ll a[NA], b[NA]; ll n, m; bool dp[NA][(1ll << N)]; void verkefni() { cin >> n >> m; for (ll i = 0; i < n; i ++) cin >> a[i]; for (ll i = 0; i < m; i ++) cin >> b[i]; for (ll mask = 0; mask < (1ll << m); mask ++) { for (ll i = 0; i < m; i ++) { if (mask & (1ll << i)) sum[mask] += b[i]; } } for (ll i = 0; i < n; i ++) { for (ll mask = 0; mask < (1ll << m); mask ++) { if (sum[mask] == a[i]) { v[a[i]].push_back(mask); } } } for (auto el : v[a[0]]) { dp[0][el] = true; } for (ll mask = 0; mask < (1ll << m); mask ++) { if (dp[0][mask]) { for (ll i = 0; i < m; i ++) { // cout << mask << " " << (mask | (1ll << i)) << nl; dp[0][mask | (1ll << i)] = true; } } } ll tot = a[0]; for (ll i = 1ll; i < n; i ++) { for (ll mask = 0; mask < (1ll << m); mask ++) { if (!dp[i-1ll][mask]) continue; if (sum[mask] - tot == a[i]) { dp[i][mask] = true; for (ll j = 0; j < m; j ++) { dp[i][mask | (1ll << j)] = true; } } } tot += a[i]; } for (ll mask = 0; mask < (1ll << m); mask ++) { if (dp[n-1ll][mask]) { cout << "YES"; return ; } } cout << "NO"; // for (ll i = 0; i < n; i ++) { // cout << a[i] << ": "; // for (auto el : v[a[i]]) { // cout << el << " "; // } // cout << nl; // } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll tst = 1ll; // cin >> tst; while (tst --) { verkefni(); cout << nl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...