Submission #870853

#	Time	Username	Problem	Language	Result	Execution time	Memory
870853		ljlkj	Bank (IZhO14_bank)	C++14	100 / 100	88 ms	8792 KiB

bank

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

int main(){
    int n , m;
    cin >> n >> m;
    vector<int> persons(n);
    vector<int> notes(m);
    for(int i = 0; i < n; i++) cin >> persons[i];
    for(int i = 0; i < m; i++) cin >> notes[i];
    
    vector<pair<int , int>> dp(1<<m);
    for(int s = 0; s < (1<<m); s++){
        dp[s].first = 0;
        dp[s].second = 0;
        for(int b = 0; b < m; b++){
             if(s&(1<<b)){
                int lastIndex = dp[s^(1<<b)].first;
                int value = dp[s^(1<<b)].second;
                // if(s == 20){
                //     cout << "last: " << lastIndex << " " << value << " note: " << notes[b] << endl;
                // }
                if(notes[b] + value == persons[lastIndex]){
                    // if(s == 20) cout << "hello5";
                    if(dp[s].first < lastIndex + 1){
                        dp[s].first = lastIndex + 1;
                        dp[s].second = 0;
                    }
                }
                else if(notes[b] + value < persons[lastIndex]){
                    // if(s == 20) cout << "hi";
                    if(dp[s].first <= lastIndex){
                        // if(s == 20) cout << "hello" << endl;
                        dp[s].first = lastIndex;
                        dp[s].second = value + notes[b];
                        // if(s == 20) cout << "ttttt: " << dp[s].second << endl;
                    }
                }
                else{
                      if(dp[s].first <= lastIndex){
                        // if(s == 20) cout << "hello" << endl;
                        dp[s].first = lastIndex;
                        dp[s].second = value + notes[b];
                        // if(s == 20) cout << "ttttt: " << dp[s].second << endl;
                    }
                }

             }
        }

    }

    // cout << "test: " << dp[20].first << endl;

    if(dp[(1<<m) - 1].first == n) cout << "YES";
    else cout << "NO";


    return 0;
}

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