Submission #870853

#TimeUsernameProblemLanguageResultExecution timeMemory
870853ljlkjBank (IZhO14_bank)C++14
100 / 100
88 ms8792 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...