Submission #469398

#	Time	Username	Problem	Language	Result	Execution time	Memory
469398		FireGhost1301	Bank (IZhO14_bank)	C++11	100 / 100	135 ms	8524 KiB

bank

/**
    __author__ : FireGhost
    problems_ID: 
 */

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;

const int N = 20 + 1;
const int MOD = 1e9 + 7;

int n, m, a[N], prf[N], b[N], dp[1 << N], sum[1 << N];

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i], prf[i] = prf[i - 1] + a[i];
    for (int i = 0; i < m; ++i)
        cin >> b[i];
    for (int msk = 1; msk < (1 << m); ++msk) {
        for (int i = 0; i < m; ++i) {
            if (msk >> i & 1) {
                sum[msk] += b[i];
                if (sum[msk ^ (1 << i)] - prf[dp[msk ^ (1 << i)] - 1] + b[i] == a[dp[msk ^ (1 << i)]])
                    dp[msk] = max(dp[msk], dp[msk ^ (1 << i)] + 1);
                else
                    dp[msk] = max(dp[msk], dp[msk ^ (1 << i)]);
            }
        }
    }
    cout << (dp[(1 << m) - 1] == n ? "YES" : "NO");
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int t = 1;
    while (t--)
        solve();
    return 0;
}

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