Submission #92771

#	Time	Username	Problem	Language	Result	Execution time	Memory
92771		SamAnd	Bank (IZhO14_bank)	C++17	100 / 100	718 ms	15656 KiB

bank

#pragma comment(linker,"/STACK:20000000")
#define _CRT_SECURE_NO_WARNINGS
#define mp make_pair
//#define OLYMP
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <cstring>
void fp();
void sp();
using namespace std;
const int N=21;

int n,m;
int a[N],b[N];
vector<int> t[N];
bool c[N][(1<<N)];
bool stg(int x,int y)
{
	for(int i=0;i<m;++i)
	{
		if((x|(1<<i))==x && (y|(1<<i))==y)
			return false;
	}
	return true;
}
int main()
{
	//fp();
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0;i<n;++i)
		cin>>a[i];
	for(int i=0;i<m;++i)
		cin>>b[i];
	//////
	for(int i=0;i<(1<<m);++i)
	{
		int x=0;
		for(int j=0;j<m;++j)
		{
			if((i|(1<<j))==i)
				x+=b[j];
		}
		for(int j=0;j<n;++j)
		{
			if(x==a[j])
				t[j].push_back(i);
		}
	}
	sort(t,t+n);
	for(int i=0;i<t[0].size();++i)
	{
		c[0][t[0][i]]=true;
	}
	for(int i=1;i<n;++i)
	{
		for(int j=0;j<t[i].size();++j)
		{
			int x=0;
			for(int k=0;k<m;++k)
			{
				if((t[i][j]|(1<<k))!=t[i][j])
					x|=(1<<k);
			}
			for(int k=(x);k;k=((k-1)&(x)))
			{
				if(c[i-1][k])
				{
					c[i][t[i][j]|k]=true;
				}
			}
		}
	}
	bool ans=false;
	for(int i=0;i<(1<<m);++i)
	{
		if(c[n-1][i])
		{
			ans=true;
			break;
		}
	}
	if(ans)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	sp();
	return 0;
}

void fp()
{
#ifndef OLYMP
	freopen("bank.in","r",stdin);
	freopen("bank.out","w",stdout);
#endif
}
void sp()
{
#ifdef OLYMP
	system("pause");
#endif
}

Compilation message (stderr)

bank.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker,"/STACK:20000000")
 
bank.cpp: In function 'int main()':
bank.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<t[0].size();++i)
              ~^~~~~~~~~~~~
bank.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<t[i].size();++j)
               ~^~~~~~~~~~~~
bank.cpp: In function 'void fp()':
bank.cpp:102:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("bank.in","r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bank.cpp:103:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("bank.out","w",stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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