Submission #1017155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017155		daviedu	Bank (IZhO14_bank)	C++17	100 / 100	96 ms	8792 KiB

bank

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

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }


signed main(){
    fastio;
    int n, m;
    cin >> n >> m;
    // people, coins
    vector<int> p (n), c (m);
    for (auto &a: p) cin >> a;
    for (auto &a: c) cin >> a;
    
    bool ans=false;
    // push dp, one dimensional
    vector<pair<int, int>> dp (1 << m, {-1, 0});
    for (int mask=0; mask<(1<<m); mask++){
        for (int i=0; i<m; i++){
            if (mask>>i&1) continue;
            int nxt = mask | (1<<i);
            pair<int, int> tmp = dp[mask];
            tmp.second += c[i];
            if (p[tmp.first+1] == tmp.second) tmp.first++, tmp.second=0;
            dp[nxt] = max(dp[nxt], tmp);
        }
        if (dp[mask].first == n-1) ans = true;
    }

    cout << (ans? "YES":"NO") << '\n';
}

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