제출 #167736

#제출 시각아이디문제언어결과실행 시간메모리
167736achibasadzishviliBank (IZhO14_bank)C++14
100 / 100
176 ms12792 KiB
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,m,a[205],b[205];
ll sum[3000005],ind[3000005],dp[3000005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        cin >> a[i];
        a[i] += a[i - 1];
    }
    a[n + 1] = a[n];
    for(int i=1; i<=m; i++){
        cin >> b[i];
    }
    sum[0] = 0;
    
    for(int i=1; i<=m; i++)
        for(int j=0; j<(1 << m); j++)
            if((j & (1 << (i - 1))) == 0)
                sum[j | (1 << (i - 1))] = sum[j] + b[i];
    
    dp[0] = 1;
    
    for(int j=0; j<(1 << m); j++){
        ll lst = 0;
        for(int i=1; i<=n; i++)
            if(a[i] <= sum[j])
                lst = i;
        ind[j] = lst;
    }
    for(int j=1; j<(1 << m); j++)
        for(int i=1; i<=m; i++)
            if(j & (1 << (i - 1)))
                if(sum[j] <= a[ind[j - (1 << (i - 1))] + 1] && dp[j - (1 << (i - 1))])
                    dp[j] = 1;
    
    for(int i=0; i<(1 << m); i++)
        if(ind[i] == n && dp[i]){
            cout << "YES";
            return 0;
        }
    
    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...