Submission #501473

#	Time	Username	Problem	Language	Result	Execution time	Memory
501473		IOI_champion_in_1980	Bank (IZhO14_bank)	C++14	100 / 100	787 ms	6796 KiB

bank

#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],dp[1050005];
vector<int> v[100005];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	for(int j=0;j<m;j++){
		cin >> b[j];
	}
	for(int mask=0;mask<(1<<m);mask++){
		int sum=0;
		for(int j=0;j<m;j++){
			if(mask&(1<<j)){
				sum+=b[j];
			}
		}
		for(int j=0;j<n;j++){
			if(sum==a[j]){
				v[j].push_back(mask);
			}
		}
	}
	dp[0]=1;
	for(int i=0;i<n;i++)
	{
//		cout<<i<<") ";
		for(int j=(1<<m);j>=0;j--)
		{
			if(dp[j]>0)
			{
				for(auto it : v[i])
				{
					if(it&j)
					{
						continue;
					}
					int x=it|j;
					dp[x]=max(dp[x],dp[j]+1);
					if(dp[x]>n)
					{
						cout <<"YES";
						return 0;
					}
				}
			}
		}
//		for (int j=0; j<=(1<<m); j++) cout<<dp[j]<<" ";
//		cout<<endl;
	}
	cout << "NO";
}

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