Submission #1209334

#TimeUsernameProblemLanguageResultExecution timeMemory
1209334starship_666Bank (IZhO14_bank)C++20
0 / 100
1095 ms2372 KiB
/////////////////////////////////////////// // // // CODE BY THE phantomstar3.14 // // // /////////////////////////////////////////// #include <bits/stdc++.h> using namespace std; #define int long long int #define ull unsigned long long std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count()); constexpr int V = 1E9; constexpr int MAXN=1e9; const int mod=1e9+7; void solve() { int n,m; cin>>n>>m; vector<int> a(n,0), b(m,0); for(int i=0; i<n; i++) cin>>a[i]; for(int i=0; i<m; i++) cin>>b[i]; bool dp[(1ll<<m)+1][n+1]; memset(dp, false, sizeof(dp)); for(int i=0; i<(1ll<<n); i++) dp[i][0]=true; for(int i=0; i<(1ll<<m); i++) { for(int j=i; j!=0; j=(j-1)&i) { int subset=(j^i); int sum=0; for(int k=0; k<m; k++) { if((1ll<<k) & subset) sum+=b[k]; } for(int k=1; k<=n; k++) { if(sum!=a[k-1]) continue; dp[i][k]|=(dp[i][k]|dp[j][k-1]); } } } for(int i=0; i<(1ll<<m); i++) { if(dp[i][n]) { cout<<"YES\n"; return; } } cout<<"NO\n"; } int32_t main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); auto begin = std::chrono::high_resolution_clock::now(); //freopen("piggyback.in", "r", stdin); //freopen("piggyback.out", "w", stdout); int t=1; //cin >> t; while (t--) { solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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...