Submission #414648

#	Time	Username	Problem	Language	Result	Execution time	Memory
414648		aaru2601	Bank (IZhO14_bank)	C++17	52 / 100	118 ms	262148 KiB

bank

#include<bits/stdc++.h>
#define lld long long
#define pb push_back
#define mk make_pair
#define MAX (lld)1e18+7
#define lim (lld)1e9+7
#define MAX2 (lld)2e5+9
#define ff first
#define ss second
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const lld mod=lim;

lld power(lld x, lld y, lld p)  
{   lld res = 1;     x = x % p; if (x == 0) return 0;  
  
    while (y > 0)  
    { if (y & 1) res = (res*x) % p;  y = y>>1; x = (x*x) % p;   }  
    return res;  } 


lld extend_gcd(lld a, lld b, lld& x, lld& y) {
    if (b == 0) { x = 1;y = 0;return a;}
    lld x1, y1;
    lld d = extend_gcd(b, a % b, x1, y1);
    x = y1; y = x1 - y1 * (a / b);return d;	}

lld modinv(lld a, lld p)
{return power(a,p-2,p);}

lld rowNum[]={-1,0,0,1};
lld colNum[]={0,-1,1,0};
int recur(vector<int>&v,vector<int>&b,vector<vector<int>>&dp,
	int cur,int val,int mask)
{
	if(cur==v.size()-1 && val==0)
		return 1;

	if(val<0)
		return 0;

	if(dp[val][mask]!=-1)
		return dp[val][mask];
	int ans = 0;
	for(int i=0;i<b.size();i++)
	{
		if((mask&(1<<i))==0)
		{
			int temp = (mask|(1<<i));
			if(val-b[i]<0)
				continue;
			if(val-b[i]==0)
				ans|=recur(v,b,dp,cur+1,v[cur+1],temp);

			if(val-b[i]>0)
				ans|=recur(v,b,dp,cur,val-b[i],temp);	
		
		}
	}

	dp[val][mask] = ans;
	return dp[val][mask];
}

int main()
{
	fastio
	int n,m;
	cin>>n>>m;
	std::vector<int> v(n+1),b(m);
	int mx = 0;
	for(int i=0;i<n;i++)
	{	
		cin>>v[i];
		mx = max(mx,v[i]);
	}
	v[n] = 0;
	for(int i=0;i<m;i++)
		cin>>b[i];
	
	vector<vector<int>>dp(mx+1,vector<int>(1<<(m+1),-1));

	int cur = 0;
	int val = v[0];
	int mask = 0;
	int res = recur(v,b,dp,cur,val,mask);

	if(res==1)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
}

Compilation message (stderr)

bank.cpp: In function 'int recur(std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, int, int, int)':
bank.cpp:37:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  if(cur==v.size()-1 && val==0)
      |     ~~~^~~~~~~~~~~~
bank.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<b.size();i++)
      |              ~^~~~~~~~~

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