Submission #1194083

#TimeUsernameProblemLanguageResultExecution timeMemory
1194083petezaBank (IZhO14_bank)C++20
100 / 100
131 ms1440 KiB
#include <bits/stdc++.h>
using namespace std;

int n, k;
int qs[21], qstgt[21];
bool vis[1<<20];

int main() {
    cin >> n >> k;
    for(int i=1;i<=n;i++) {cin >> qstgt[i]; qstgt[i] += qstgt[i-1];}
    for(int i=1;i<=k;i++) {cin >> qs[i];}
    vis[0] = 1;
    for(int cst=0;cst<(1<<k);cst++) {
        if(!vis[cst]) continue;
        //cout << cst << '\n';
        int idx = 0, sum = 0;
        for(int i=0;i<k;i++) if((cst>>i)&1) sum += qs[i+1];
        for(idx=0;idx<=n && qstgt[idx] <= sum;idx++); idx--;
        if(idx == n) {cout << "YES"; return 0;}
        for(int i=0;i<k;i++) {
            if(cst & (1 << i)) continue;
            if(sum + qs[i+1] > qstgt[idx+1]) continue;
            vis[cst | (1 << i)] = 1;
        }
    }
    cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...