Submission #1239849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239849		nastya_an	Bank (IZhO14_bank)	C++20	0 / 100	47 ms	45376 KiB

bank

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define cin(v) \
    for (auto &el : v) { cin >> el; }
#define cout(v)                               \
    for (auto &el : v) { cout << el << " "; } \
    cout << "\n";

using namespace std;
using ll = long long;
using db = double;
using ldb = long double;
const ldb EPS = 1e-9;
const ll LINF = 2e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 1072005019;
const ll MOD3 = 998244353;
const ldb PI = acos(-1.0);

int dp[21][1 << 20];

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    cin(a);
    cin(b);
    n++; m++;
    a.push_back(1e9);
    b.push_back(1e9);
    for (int i = 0; i < n; i++) {
        fill(dp[i], dp[i] + (1 << m),2e9);
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << m); mask++) {
            if (dp[i][mask] == 2e9) {
                continue;
            }
            for (int nxt = 0; nxt < m; nxt++) {
                if ((mask >> nxt) & 1) {
                    continue;
                }
                if (dp[i][mask] + b[nxt] <= a[i]) {
                    dp[i][mask | (1 << nxt)] = min(dp[i][mask | (1 << nxt)], dp[i][mask] + b[nxt]);
                } else {
                    if (dp[i][mask] == a[i] && b[nxt] <= a[i + 1]) {
                        dp[i + 1][mask | (1 << nxt)] = min(dp[i + 1][mask | (1 << nxt)], b[nxt]);
                    }
                }
            }
        }
    }
    for (int mask = 0; mask < (1 << m); mask++) {
        if (dp[n - 1][mask] != 2e9) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
    return;
}

signed main() {
    ll interactive = 0;
    ll multitest = 0;
    if (!interactive) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
//#ifdef LOCAL
        freopen("bank.in", "r", stdin);
        freopen("bank.out", "w", stdout);
//#endif
    }
    if (multitest) {
        ll T;
        cin >> T;
        while (T--) {
            solve();
        }
    } else {
        solve();
    }
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen("bank.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen("bank.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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