Submission #598416

#	Time	Username	Problem	Language	Result	Execution time	Memory
598416		jack715	Bank (IZhO14_bank)	C++14	100 / 100	179 ms	16844 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), dp(1<<m, -1), leftover(1<<m, -1);
    for (int i = 0; i < n; i++)
        cin >> people[i];
    for (int i = 0; i < m; i++)
        cin >> money[i];

    dp[0] = leftover[0] = 0;
    for(int b = 0; b < (1<<m); b++) {
        for (int i = 0; i < m; i++) {
            if (b&(1<<i) == 0) continue;

            int last = b^(1<<i), tot = leftover[last]+money[i];
            if (dp[last] == -1) continue;
            if (tot < people[dp[last]]) {
                dp[b] = dp[last];
                leftover[b] = tot;
            } else if (tot == people[dp[last]])
                dp[b] = dp[last]+1, leftover[b] = 0;
        }
        if (dp[b] == n) {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\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
*/

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:29:26: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   29 |             if (b&(1<<i) == 0) continue;
      |                   ~~~~~~~^~~~

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