Submission #342648

#	Time	Username	Problem	Language	Result	Execution time	Memory
342648		apostoldaniel854	Bank (IZhO14_bank)	C++14	100 / 100	178 ms	1516 KiB

bank

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
const int MX = 1e3, MAX_N = 20;
const int MAX_SUM = MAX_N * MX;
int salary[1 + MAX_N];
int sum[1 + MAX_N];
int bill[MAX_N];
int progress[1 + MAX_SUM];
bool dp[1 << MAX_N];

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> salary[i];
        sum[i] = sum[i - 1] + salary[i];
        progress[sum[i]] = i;
    }
    for (int i = 1; i <= MAX_SUM; i++)
        if (not progress[i])
            progress[i] = progress[i - 1];
    for (int i = 0; i < m; i++)
        cin >> bill[i];
    dp[0] = true;
    bool good = false;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (dp[mask]) {
            int paid = 0;
            for (int i = 0; i < m; i++)
                if (mask & (1 << i))
                    paid += bill[i];
            for (int i = 0; i < m; i++)
                if (not (mask & (1 << i))) {
                    int new_paid = paid + bill[i];
                    int new_mask = mask ^ (1 << i);
                    if (progress[paid] == progress[new_paid])
                        dp[new_mask] = true;
                    else {
                        if (progress[paid] + 1 == progress[new_paid] && sum[progress[new_paid]] == new_paid) {
                            dp[new_mask] = true;
                            if (progress[new_paid] == n)
                                good = true;
                        }
                    }
                }
        }
    }
    if (good)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}

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