제출 #1001378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001378		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	86 ms	19032 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 21;
ll dp[(1LL<<mxn)], a[mxn], b[mxn], s_b[(1LL<<mxn)];
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    ll n, m; cin >> n >> m;
    for (ll i = 0; i < n; i++) {cin >> a[i]; a[i] += a[i-1];}
    for (ll i = 0; i < m; i++) cin >> b[i];
    for (ll i = 0; i < (1LL<<m); i++) 
    {
        for (ll j = 0; j < m; j++) s_b[i] += b[j]*(i>>j&1);
    }
    dp[0] = 1;
    for (ll i = 0; i < (1LL<<m); i++)
    {
        if (!dp[i]) continue;
        ll diff = *upper_bound(a,a+n,s_b[i])-s_b[i];
        for (ll j = 0; j < m; j++)
        {
            if (!(i>>j&1) && b[j] <= diff) dp[i^(1LL<<j)] = 1;
        }
    }
    bool ck = 0;
    for (ll i = 0; i < (1LL<<m); i++) ck |= (s_b[i] == a[n-1] && dp[i]);
    if (ck) cout << "YES";
    else cout << "NO";
}

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