Submission #1249192

#TimeUsernameProblemLanguageResultExecution timeMemory
1249192kitsuneBank (IZhO14_bank)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> /// kitsune using namespace std; #define fi first #define se second #define mp make_pair //#define int long long #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++) #define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--) typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; } template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; } const int siz = 1e5 + 2; const int SIZ = 1e6 + 2; const int mod = 1e9 + 7; const int maxx = 2e9; const ll MAXX = 1e18; const string file = "1"; int a[24], b[24]; int s[1 << 24]; bool dp[1 << 24]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); // if (fopen((file + ".inp").c_str(), "r")) { // freopen((file + ".inp").c_str(), "r", stdin); // freopen((file + ".out").c_str(), "w", stdout); // } int n, m; cin >> n >> m; rep (i, 0, n - 1) { cin >> a[i]; } rep (i, 0, m - 1) { cin >> b[i]; } sort(a, a + n); sort(b, b + m); for (int i = 0, j = 0; i < n && j < m; i++) { while (b[j] < a[i]) { j++; } if (b[j] == a[i]) { b[j] = a[i] = -1; j++; } } for (int i = 0, j = 0; j < n; i++) { if (a[i] != -1) { continue; } maximize(j, i + 1); while (j < n && a[j] != -1) { j++; } if (j == n) { n = i; break; } swap(a[i], a[j]); } for (int i = 0, j = 0; j < m; i++) { if (b[i] != -1) { continue; } maximize(j, i + 1); while (j < m && b[j] != -1) { j++; } if (j == m) { m = i; break; } swap(b[i], b[j]); } rep (i, 0, n - 1) { a[i] += (i == 0 ? 0 : a[i - 1]); } rep (mask, 1, (1 << m) - 1) { int k = __builtin_ctz(mask); s[mask] = s[mask ^ (1 << k)] + b[k]; } per (mask, (1 << m) - 1, 0) { int pos = upper_bound(a, a + n, s[mask]) - a; if (pos == n) { dp[mask] = true; continue; } dp[mask] = false; for (int tmp = ((1 << m) - 1) ^ mask, i = __builtin_ctz(tmp); tmp; tmp ^= 1 << i, i = __builtin_ctz(tmp)) { int new_mask = mask ^ (1 << i); if (s[new_mask] <= a[pos]) { dp[mask] |= dp[new_mask]; } } } cout << (dp[0] ? "YES" : "NO") << "\n"; // cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...