Submission #1303872

#TimeUsernameProblemLanguageResultExecution timeMemory
1303872ChottuFBank (IZhO14_bank)C++20
100 / 100
89 ms8612 KiB
#include <bits/stdc++.h>
using namespace std;

pair<int,int> dp[1<<20];

int main(){
    int n,m;
    cin >> n >> m;
    int arr[n];
    int note[m];
    for (int i = 0; i<n; i++){
        cin >> arr[i];
    }
    for (int i = 0; i<m; i++){
        cin >> note[i];
    }
    sort(arr,arr+n);
    sort(note,note+m);
    dp[0] = {0,0}; //we're at index 0, still there
    for (int s = 1; s<(1<<m); s++){
        dp[s] = {-1,-1}; //we want to maximise first
        for (int p = 0; p<m; p++){
            if ((s & (1<<p)) == 0) continue;
            int prv = s ^ (1<<p);
            if (dp[prv].first == -1 || dp[prv].second == -1) continue;
            auto [idx,lft] = dp[prv];
            if (lft + note[p] < arr[idx]){
                lft = lft+note[p];
            }
            else if (lft + note[p] == arr[idx]){
                lft = 0;
                idx++;
                if (idx == n){
                    cout << "YES\n";
                    return 0;
                }
            }
            else if (lft + note[p] > arr[idx]){
                continue;
            }
            dp[s] = max(dp[s], {idx,lft});
        }
    }
    cout << "NO\n";
    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...