Submission #947572

#	Time	Username	Problem	Language	Result	Execution time	Memory
947572		pcc	Bank (IZhO14_bank)	C++17	100 / 100	221 ms	4548 KiB

bank

#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";
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29