Submission #856231

#	Time	Username	Problem	Language	Result	Execution time	Memory
856231		AverageAmogusEnjoyer	Bank (IZhO14_bank)	C++17	100 / 100	91 ms	8640 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=20;
int dp[1<<N][2]; // first to do, remained money
int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    vector<int> people(n),money(m);
    for (int &x: people) {
        cin >> x;
    }
    for (int &x: money) {
        cin >> x;
    }
    for (int i=1;i<(1<<m);i++) {
        for (int j=0;j<m;j++) {
            if (i & (1<<j)) {
                int to_do=dp[i^(1<<j)][0],rem=dp[i^(1<<j)][1];
                if (rem+money[j]==people[to_do]) {
                    if (cmax(dp[i][0],to_do+1)) {
                        dp[i][1]=0;
                    }
                } else if (money[j]==people[to_do]) {
                    if (cmax(dp[i][0],to_do+1)) {
                        dp[i][1]=rem;
                    }
                } else if (to_do>=dp[i][0]) {
                    dp[i][0]=to_do;
                    dp[i][1]=rem+money[j];
                }
            }
        }
        if (dp[i][0] == n) {
            cout << "YES\n";
            return 0;
        }
    }
    /*
    for (int i=1;i<(1<<m);i++) {
        cout << bitset<8>(i) << " " << dp[i][0] << " " << dp[i][1] << "\n";
    }
    */
    cout << "NO\n";
}

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