Submission #1298941

#TimeUsernameProblemLanguageResultExecution timeMemory
1298941khanhphucscratchBank (IZhO14_bank)C++20
100 / 100
136 ms4528 KiB
#include<bits/stdc++.h>
using namespace std;
bool getbit(int num, int bit)
{
    return (num >> bit)&1;
}
int flipbit(int num, int bit)
{
    return num ^ (1 << bit);
}
int a[25], b[25], val[20005], dp[1 << 20];
bool valid(int x, int y)
{
    return val[x+1] == val[x+y];
}
int main()
{
    int m, n; cin>>m>>n;
    for(int i = 1; i <= m; i++) cin>>a[i];
    for(int i = 1; i <= n; i++) cin>>b[i];
    int cur = 0;
    for(int i = 1; i <= m; i++){
        for(int j = cur+1; j <= cur+a[i]; j++) val[j] = i;
        cur += a[i];
    }
    dp[0] = 1;
    bool ok = 0;
    for(int i = 0; i < (1 << n); i++) if(dp[i] == 1){
        int sum = 0;
        for(int j = 0; j < n; j++) if(getbit(i, j) == 1) sum += b[j+1];
        for(int j = 0; j < n; j++) if(getbit(i, j) == 0 && valid(sum, b[j+1]) == 1){
            dp[flipbit(i, j)] = 1;
        }
        if(sum == cur) ok = 1;
    }
    if(ok == 1) cout<<"YES";
    else 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...