Submission #863569

#TimeUsernameProblemLanguageResultExecution timeMemory
863569Mohammadamin__Sh은행 (IZhO14_bank)C++17
0 / 100
1085 ms2764 KiB
//In His Name
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//#define int ll
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
#define ceil(x,y) x/y + min(1ll,x%y)
const int maxn = 22 , MOD = 1e9 + 7;
const ll INF = 1e18;

int n , m , a[maxn] , c[maxn] , ps[maxn] , dp[(1<<maxn)] , ok = 0;

int main(){
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    for(int i = 0 ; i < m ; i++) cin >> c[i];
    for(int i = 1 ; i <= n ; i++) ps[i] = ps[i-1] + a[i];
    for(int mask = 1 ; mask < (1 << m) - 1 ; mask++){
        int maxi = 0 , sum = 0 , cnt = m-1 , tmp = mask;
        for(int sub = mask ; sub > 0 ; ((sub-=1) &= mask))  maxi = max(maxi , dp[sub]);
        while(tmp > 0){
            if(tmp & 1) sum += c[cnt];
            cnt --;
            tmp >>= 1;
        }
        if(sum == ps[maxi+1]) dp[mask] = maxi + 1;
        else dp[mask] = maxi;
        if(dp[mask] == n){
            ok = 1;
            break;
        }
    }
    cout << (ok ? "YES" : "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...