제출 #947572

#제출 시각아이디문제언어결과실행 시간메모리
947572pcc은행 (IZhO14_bank)C++17
100 / 100
221 ms4548 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 20;
int dp[1<<21];
int note[mxn];
int pref[mxn];
int N,M;

bool btw(int a,int b){
	for(int i = 0;i<N;i++){
		if(pref[i]>a&&pref[i]<b)return true;
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 0;i<N;i++)cin>>pref[i],pref[i] = (i?pref[i]+pref[i-1]:pref[i]);
	for(int i = 0;i<M;i++)cin>>note[i];
	for(int i = 0;i<(1<<M);i++){
		for(int j = 0;j<M;j++){
			if(i&(1<<j))continue;
			if(!btw(dp[i],dp[i]+note[j]))dp[i|(1<<j)] = max(dp[i|(1<<j)],dp[i]+note[j]);
		}
	}
	if(*max_element(dp,dp+(1<<M)) >= pref[N-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...