Submission #1280093

#TimeUsernameProblemLanguageResultExecution timeMemory
1280093blacktulipBank (IZhO14_bank)C++17
100 / 100
185 ms16876 KiB
//Hello!..
//dört böler altı artı iki ama ne böler altı ne böler iki
//Başarı, Boş Duranın Hakkı Değil... Koşturanın Hakkıdır. Hakan?
//Ne yapayım, elimden gelen bu :(
//S'il vous plait
#include <bits/stdc++.h>
using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define int long long
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define setrandom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define getrandom(a,b) uniform_int_distribution<int>(a,b)(rng)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
#define _ << " " <<

const lo inf = 1000000000;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,b[li],val[1<<20],dp[1<<20],PS[li];
int cev;
string s;
vector<int> v;

inline int f(int sira,int mask){
	if(sira>n)return 1;
	if(~dp[mask])return dp[mask];
	int cevv=0;
	for(int i=0;i<m;i++){
		if(mask&(1<<i))continue;
		int at=mask|(1<<i);
		if(val[at]<PS[sira])cevv|=f(sira,at);
		else if(val[at]==PS[sira])cevv|=f(sira+1,at);
	}
	return dp[mask]=cevv;
}

int32_t main(){
	fio();
	cin>>n>>m;
	FOR{cin>>a[i];PS[i]=PS[i-1]+a[i];}
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<m;i++)cin>>b[i];
	for(int i=0;i<(1<<m);i++){
		int say=0;
		for(int j=0;j<m;j++){
			if(i&(1<<j))say+=b[j];
		}
		val[i]=say;
	}
	cev=f(1,0);
	if(cev)cout<<"YES\n";
	else cout<<"NO\n";
	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...