제출 #1329240

#제출 시각아이디문제언어결과실행 시간메모리
1329240ahmetlbktd4은행 (IZhO14_bank)C++20
100 / 100
84 ms8640 KiB
#include "bits/stdc++.h"
#define ff first
#define ss second
#define ll long long 
using namespace std;

const int N = 20;
const int inf = 1e9+1;

int dp[1<<N],sm[1<<N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("file.in","r",stdin);
    int n,m;
    cin >> n >> m;
    int a[n];
    for (int i = 0;i < n;i++){
        cin >> a[i];
    }
    int b[m];
    for (int i = 0;i < m;i++){
        cin >> b[i]; 
    } 
    memset(dp,-1,sizeof(dp));
    dp[0] = 0;
    sm[0] = 0;
    for (int mask = 0;mask < (1<<m);mask++){
        if (dp[mask] == -1)
        continue;
        for (int i = 0;i < m;i++){
            if (!(mask & (1<<i))){
                int h = mask|(1<<i);
                int l = dp[mask];
                int s = sm[mask] + b[i];
                if (l == n)
                continue;
                if (s < a[l]){
                    dp[h] = l;
                    sm[h] = s;
                }
                else if (s == a[l]){
                    dp[h] = l+1;
                    sm[h] = 0;
                }
            }
        }
        if (dp[mask] == n){
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...