제출 #1241787

#제출 시각아이디문제언어결과실행 시간메모리
1241787cokalhado은행 (IZhO14_bank)C++20
100 / 100
133 ms4516 KiB
// 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...