Submission #697598

#	Time	Username	Problem	Language	Result	Execution time	Memory
697598		Tam_theguide	Bank (IZhO14_bank)	C++14	100 / 100	102 ms	8608 KiB

bank

#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";
}

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