Submission #167009

#	Time	Username	Problem	Language	Result	Execution time	Memory
167009		Dovran	Bank (IZhO14_bank)	C++11	44 / 100	27 ms	23928 KiB

bank

#include <bits/stdc++.h>
#define N 1000009
#define pii pair <int, int>
#define ff first
#define ss second
#define pb push_back
#define pp pop_back
#define ll long long

using namespace std;

int n, m, v[N], c[N], b[N], mxx;
int vis[N];
vector<int>e[N];
bool asd;
vector<int>bt;
map<vector<int>, int>vss;

void pr(int x, int y);

void f(int x){
	if(x==n+1){
		cout<<"YES\n";
		asd=1;
		return;
	}
	b[0]=1;
	for(int i=1; i<=m; i++){
		if(vis[c[i]]>0){
			for(int j=v[x]; j>=0; j--){
				if(b[j]==1)
					e[j+c[i]].pb(c[i]), b[j+c[i]]=1;
			}
		}
	}
	pr(v[x], x);
	for(int i=1; i<=mxx+v[x]; i++)
		e[i].clear(), b[i]=0;
}

void pr(int x, int y){
	if(x==0){
		vector<int>asd=bt;
		sort(asd.begin(), asd.end());
		if(vss[asd]==0)
			f(y+1), vss[bt]=1;
		return;
	}
	for(auto i:e[x]){
		if(vis[i] > 0)
			vis[i]--, bt.pb(i), pr(x-i, y), bt.pp(), vis[i]++;
		if(asd==1)
			break;
	}
}

int main(){
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		cin>>v[i];

	for(int i=1; i<=m; i++)
		cin>>c[i], vis[c[i]]++, mxx=max(mxx, c[i]);
	f(1);
	if(asd==0)
		cout<<"NO\n";
}
/*
1 5
8
4 2 5 1 3
*/

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