제출 #1241787

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

bank

// https://oj.uz/problem/view/IZhO14_bank
#include<bits/stdc++.h>
using namespace std;

const int maxn = 20;
int dp[(1<<maxn)];
int ar[maxn];
int br[maxn];
int N, M;
bool ans;

int main()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++)
    {
        cin >> ar[i];
    }
    for(int i = 0; i < M; i++)
    {
        cin >> br[i];
    }
    dp[0] = 1;
    for(int mask = 0; mask < (1<<M); mask++)
    {
        // cout << "mask " << mask << " bool " << dp[mask] << endl;
        if(!dp[mask]) continue;
        int i = 0;
        int s = 0;
        for(int j = 0; j < M; j++)
        {
            if((1<<j)&mask) s += br[j];
        }
        for(; i < N; i++)
        {
            if(ar[i] <= s) s -= ar[i];
            else break;
        }
        if(i == N)
        {
            ans = 1;
            break;
        }
        for(int j = 0; j < M; j++)
        {
            if((1<<j)&mask) continue;
            if(br[j]+s <= ar[i]) dp[mask+(1<<j)] = 1;
            // cout << "j " << j << " mask+j " << mask+(1<<j) << " bool " << dp[mask+(1<<j)] << endl;
        }
    }
    cout << (ans ? "YES" : "NO");
    return 0;
}

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