Submission #783621

#	Time	Username	Problem	Language	Result	Execution time	Memory
783621		abhinavshukla408	Bank (IZhO14_bank)	C++14	100 / 100	129 ms	16724 KiB

bank

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <math.h>
 
using namespace std;
 
#define endl "\n"
#define int int64_t 
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR0(i,a) FOR(i,0,a)
#define FOR1(i,a) for (int i = (1); i <= (a); ++i)
#define TRAV(a,x) for (auto& a: x)

using pii = pair<int,int>;
using vi = vector<int>;

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int salary_count,note_count;
	cin>>salary_count>>note_count;
	vi salary(salary_count),notes(note_count);
	FOR0(i,salary_count){cin>>salary[i];}
	FOR0(i,note_count){cin>>notes[i];}

	int dp1[1<<note_count];
	int dp2[1<<note_count];

	FOR0(i,1<<note_count){
		dp1[i]=0;
		dp2[i]=0;
	}

	FOR0(i,1<<note_count){
		FOR0(j,note_count){
			if(dp1[i]==(salary_count)){
				cout<<"YES"<<endl;
				return 0;
			}
			if(i & (1<<j)){
				int old=i & ~(1<<j);
				if(dp1[old]>dp1[i]){
					dp1[i]=dp1[old];
					dp2[i]=dp2[old];
				}
				int curLeft=dp2[old]+notes[j];
				if(salary[dp1[old]]==curLeft && (dp1[old]+1)>dp1[i]){
					dp2[i]=0;
					dp1[i]=dp1[old]+1;
				}else if(salary[dp1[old]]>curLeft && dp1[old]>=dp1[i]){
					dp1[i]=dp1[old];
					dp2[i]=curLeft;
				}
			}
		}
		if(dp1[i]==(salary_count)){
			cout<<"YES"<<endl;
			return 0;
		}
	}
	// FOR0(i,1<<note_count){
	// 	cout<<i<<" "<<dp1[i]<<" "<<dp2[i]<<endl;
	// }
	cout<<"NO"<<endl;
	
	



	return 0;
}

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