제출 #1194559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194559		_sieg_	Bank (IZhO14_bank)	C++20	100 / 100	486 ms	223740 KiB

bank

//           ▓▓▓▓▓▓▓▓▓    ▓▓▓    ▓▓▓▓▓▓▓▓▓▓    ▓▓▓▓▓▓▓▓                                                      
//          ▓▓            ▓▓▓    ▓▓▓           ▓▓                                                         
//           ▓▓▓▓▓▓▓▓     ▓▓▓    ▓▓▓▓▓▓▓       ▓▓   ▓▓▓▓                                               
//                  ▓▓    ▓▓▓    ▓▓▓           ▓▓    ▓▓                                            
//  ▄▄▄▄▄▄  ▓▓▓▓▓▓▓▓▓     ▓▓▓    ▓▓▓▓▓▓▓▓▓▓    ▓▓▓▓▓▓▓▓   ▄▄▄▄▄▄     
#define _USE_MATH_DEFINES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#define ff first
#define ss second
#define cc continue
#define pb push_back
#define ins insert
#define endl cout << endl;
#define all(a) (a).begin(), (a).end()
#define parz(n) [](int x) { for(int i = 2; i * i <= x; ++i) if(x % i == 0) return false; return x > 1; }(n)
#define replr(i, a, b) for (ll i = ll(a); i <= ll(b); ++i)
#define reprl(i, a, b) for (ll i = ll(a); i >= ll(b); --i)
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define mkp(a, b) make_pair(a, b)
#define no {cout << "NO\n";return;}
#define yes {cout << "YES\n";return;}
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef vector<ll> VI;
typedef vector<bool> VB;
typedef vector<string> VS;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;


void solve() {
    int n,m; cin >> n >> m;
    VL a(n),b(m);
    rep(i,n)cin >> a[i];
    rep(i,m)cin >> b[i];
    VVL ans(200001),dp(1<<m,VL(n));
    rep(i,(1 << m)){
        ll cnt = 0;
        rep(j,m)cnt+=((i & (1 << j)) != 0) * b[j];
        ans[cnt].pb(i);
    }
    for(auto x : ans[a[0]])dp[x][0] = 1;
    rep(i,(1 << m)){
        replr(j,1,n-1){
            if(dp[i][j-1]){
                for(auto x : ans[a[j]]){
                    if((i & x) == 0){dp[i+x][j] = 1;}
                }
            }
        }
    }
    rep(i,(1 << m))if(dp[i][n-1])yes
    no
}
    
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ll _ = 1;
    // cin >> _;
    while (_--)solve();
}
/*
 
*/

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29