제출 #697598

#제출 시각아이디문제언어결과실행 시간메모리
697598Tam_theguide은행 (IZhO14_bank)C++14
100 / 100
102 ms8608 KiB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
const int N = 20;
int n, m, a[N+2], b[N+2];
pii dp[(1<<N)+2];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n;i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    dp[0]={1, 0};
    for (int mask = 0; mask < (1<<m); mask++) {
        if (dp[mask].fi==0) continue;
        if (dp[mask].fi==n+1) return cout << "YES",0;
        for (int i = 0; i < m; i++)
        if (!(mask&(1<<i))) {
            if (dp[mask].se+b[i]>a[dp[mask].fi]) continue;
            else if (dp[mask].se+b[i]==a[dp[mask].fi])
            dp[mask^(1<<i)] = max(dp[mask^(1<<i)], {dp[mask].fi+1, 0});
            else dp[mask^(1<<i)]=max(dp[mask^(1<<i)], {dp[mask].fi, dp[mask].se+b[i]});
        }
    }
    cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...