Submission #598112

#	Time	Username	Problem	Language	Result	Execution time	Memory
598112		jack715	Bank (IZhO14_bank)	C++14	71 / 100	1083 ms	17372 KiB

bank

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
#define int long long

using namespace std;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("bank.in", "r", stdin);
    // freopen("bank.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<int> people(n), money(m);
    for (int i = 0; i < n; i++)
        cin >> people[i];
    for (int i = 0; i < m; i++)
        cin >> money[i];

    vector<vector<int> > make(1005), dp(n+1);
    for (int b = 0; b < (1<<m); b++) {
        int now = 0;
        for (int j = 0; j < m; j++)
            if (b&(1<<j)) now += money[j];
        if (now <= 1000)
            make[now].pb(b);
    }
    dp[0].pb(0);
    for (int i = 0; i < n; i++) {
        for (int state : dp[i]) {
            for (int b : make[people[i]]) {
                if ((b^state) < (b+state)) continue;
                dp[i+1].pb(b^state);
            }    
        }
    }

    if (dp[n].empty())
        cout << "NO\n";
    else 
        cout << "YES\n";
    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

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