제출 #1132908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132908		DangKhoizzzz	은행 (IZhO14_bank)	C++20	100 / 100	100 ms	8560 KiB

bank

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define ar3 array <int , 3>

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 2e5 + 7;


int n , m , a[40] , b[40];
pii dp[(1 << 21)];

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];

    a[n+1] = INF;

    dp[0] = {0 , 0};

    for(int mask = 1; mask < (1 << m); mask++)
    {
        for(int i = 0; i < m; i++)
        {
            if(((mask >> i)&1) == 0) continue;

            pii prev = dp[mask ^ (1 << i)];

            if((prev.se + b[i]) == a[prev.fi + 1])
            {
                dp[mask] = max(dp[mask] , {prev.fi + 1 , 0});
            }
            else
            {
                dp[mask] = max(dp[mask] , {prev.fi , prev.se + b[i]});
            }
        }
    }

    for(int i = 0; i < (1 << m); i++)
    {
        if(dp[i].fi == n)
        {
            cout << "YES" << '\n'; return;
        }
    }
    cout << "NO" << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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