제출 #1001899

#제출 시각아이디문제언어결과실행 시간메모리
1001899idkman은행 (IZhO14_bank)C++17
0 / 100
1 ms604 KiB
// #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #define ll long long #define For(i,a,b) for(ll i=(a);i<=(b);i++) #define Ford(i,a,b) for(ll i=(a);i>=(b);i--) #define inf 1000000000000000000 #define pb push_back #define all(x) x.begin(), x.end() #define fi first #define se second #define endl "\n" using namespace std; int Dx[] = {0, 1, 0, -1, -1, -1, 1, 1}; int Dy[] = {-1, 0, 1, 0, 1, -1, 1, -1}; int dx[] = {0, 1, 0, -1}; int dy[] = {-1, 0, 1, 0}; const ll N = 100000; const int block_size = 300; const int MOD = 1e9 + 7; /* 998244353 */ const int LOG = 31; const int K = 20; ll nph(ll k, ll x) { return ((x >> k) & 1); } ll n,m,a[25],b[25]; pair<ll, ll> dp[1<<20]; void Solve() { cin>>n>>m; For(i, 0, n-1) cin>>a[i]; For(i, 0, m-1) cin>>b[i]; For(i, 0, (1 << m) - 1) dp[i] = {0, 0}; dp[0] = {0, 0}; for(ll mask = 1; mask < (1 << m); mask++) { for(ll last = 0; last < m; last++) { if(nph(last, mask)) { ll oldmask = mask ^ (1 << last); ll need = a[dp[oldmask].fi + 1]; ll have = dp[oldmask].se + b[last]; if(have == need) { dp[mask].fi = max(dp[mask].fi, dp[oldmask].fi + 1); dp[mask].se = 0; } else { dp[mask].fi = dp[oldmask].fi; dp[mask].fi = have; } } } if(dp[mask].fi == n) {cout << "YES"; return;} } cout << "NO"; } int main() { // freopen("SUMMAX.inp", "r", stdin); // freopen("SUMMAX.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin>>t; while(t--) { Solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...