Submission #335645

#TimeUsernameProblemLanguageResultExecution timeMemory
335645OlerinskiyBank (IZhO14_bank)C++14
100 / 100
547 ms12800 KiB
#include <iostream> #include <iomanip> #include <algorithm> #include <bitset> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <cmath> #include <time.h> #include <random> #include <string> #include <cassert> #include <vector> #include <ostream> #include <istream> #include <stack> #include <deque> #include <queue> #include <functional> #include <chrono> #include <stack> using namespace std; // #define int long long #define pb push_back #define all(a) (a).begin(), (a).end() #define pii pair<int, int> #define ld long double ostream& operator<< (ostream &out, const vector<int> &b) { for (auto k : b) out << k << " "; return out; } istream& operator>> (istream& in, pii& b) { in >> b.first >> b.second; return in; } ostream& operator<< (ostream& out, const pii& b) { out << "{" << b.first << ", " << b.second << "}"; return out; } template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;} template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;} #ifdef LOCAL #define dbg(x) cout << #x << " : " << (x) << endl; // const int INF = 1e18; // const int mod = 2600000069; // const int p = 10; #else #define dbg(x) 57 // const int INF = 1e18; // const int mod = 2600000069; // const int p = 179; #endif const ld PI = 4 * atan(1); #define time clock() / (double) CLOCKS_PER_SEC // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC target("sse,sse2,sse3,sse3,sse4") // #pragma GCC optimize("unroll-loops") // #pragma GCC optimize("fast-math") // #pragma GCC target("avx2") // #pragma GCC optimize("section-anchors") // #pragma GCC optimize("profile-values,profile-reorder-functions,tracer") // #pragma GCC optimize("vpt") // #pragma GCC optimize("rename-registers") // #pragma GCC optimize("move-loop-invariants") // #pragma GCC optimize("unswitch-loops") // #pragma GCC optimize("function-sections") // #pragma GCC optimize("data-sections") mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count()); const int MAXN = 20; int n, m; int a[MAXN], b[MAXN]; vector<int> go[MAXN]; int mx[(1 << MAXN)], lft[(1 << MAXN)], suf[MAXN], ppc[(1 << MAXN)]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; int suma = 0, sumb = 0; for (int i = 0; i < n; i++) { cin >> a[i]; suma += a[i]; } for (int i = 0; i < m; i++) { cin >> b[i]; sumb += b[i]; } suf[n - 1] = a[n - 1]; for (int i = n - 2; i >= 0; i--) { suf[i] = suf[i + 1] + a[i]; } if (n > m || suma > sumb) { cout << "NO\n"; return 0; } for (int i = 0; i < (1 << m); i++) { ppc[i] = __builtin_popcount(i); int sum = 0; for (int j = 0; j < m; j++) { if ((i >> j) & 1) { sum += b[j]; } } for (int j = 0; j < n; j++) { if (sum == a[j]) { go[j].pb(i); } } lft[i] = sumb - sum; } for (int i = 0; i < (1 << m); i++) { if (mx[i] == n) { cout << "YES\n"; return 0; } if (suf[mx[i]] > lft[i] || m - ppc[i] < n - mx[i]) continue; for (auto mask : go[mx[i]]) { if (!(mask & i)) { chkmax(mx[i | mask], mx[i] + 1); } } } cout << "NO\n"; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...