Submission #555806

#	Time	Username	Problem	Language	Result	Execution time	Memory
555806		Alma	Bank (IZhO14_bank)	C++17	71 / 100	1077 ms	82396 KiB

bank

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

#define fi first
#define se second
using ll = long long;
using ii = pair<int,int>;

const int INF = 1e9;
const ll LLINF = 1e18;
using vi = vector<int>;
using vvi = vector<vi>;

void setIO (string fileName) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if (fileName != "std") {
        freopen((fileName + ".in").c_str(), "r", stdin);
        freopen((fileName + ".out").c_str(), "w", stdout);
    }
}

int N, M;
int a[20], b[20], pre[20];
int dp[20][(1 << 20)];

int main() {
    setIO("std");

    memset(pre, 0, sizeof pre);
    memset(dp, -1, sizeof dp);
    dp[0][0] = 0;

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        if (i == 0) pre[i] = a[i];
        else pre[i] = a[i] + pre[i-1];
    }
    for (int i = 0; i < M; i++) {
        cin >> b[i];
    }

    for (int i = 0; i < N; i++) {
        for (int mask = 0; mask < (1 << M); mask++) {
            for (int p = 0; p < M; p++) {
                if (!(mask & (1 << p))) continue;

                int x = mask - (1 << p);
                if (i > 0 and dp[i-1][x] == pre[i-1]) dp[i][mask] = dp[i-1][x] + b[p];
                if (dp[i][x] != -1 and dp[i][x] + b[p] <= pre[i]) dp[i][mask] = dp[i][x] + b[p];
            }
        }
    }

    for (int mask = 0; mask < (1 << M); mask++) {
        if (dp[N-1][mask] == pre[N-1]) {
            cout << "YES\n";
            return 0;
        }
        // cerr << mask << ": " << dp[0][mask] << '\n';
    }
    cout << "NO\n";

    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'void setIO(std::string)':
bank.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen((fileName + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((fileName + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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