제출 #886277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886277		dwuy	은행 (IZhO14_bank)	C++14	100 / 100	60 ms	21924 KiB

bank

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

int n, m;
int a[50];
int b[50];
int pf[50];
bool f[MASK(20)][21];

void nhap(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i], pf[i] = pf[i-1] + a[i];
    for(int i=0; i<m; i++) cin >> b[i];
}

void solve(){
    f[0][0] = 1;
    bool ans = 0;
    for(int mask=1; mask<MASK(m); mask++){
        int sum = 0;
        for(int t=mask; t; t-=-t&t) sum += b[__lg(-t&t)];
        int i=0;
        while(i<=n && pf[i]<sum) i++;
        if(i>n) continue;
        for(int t=mask; t; t-=-t&t){
            int Mask = mask^(-t&t);
            int pre = sum - b[__lg(-t&t)];
            if(f[Mask][i] || (pre==pf[i-1] && f[Mask][i-1])){
                f[mask][i] = 1;
                break;
            }
        }
        if(sum == pf[n] && i==n && f[mask][i]) ans = 1;
    }
    cout << (ans? "YES":"NO");
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

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