Submission #858141

#TimeUsernameProblemLanguageResultExecution timeMemory
858141vjudge1Bank (IZhO14_bank)C++17
100 / 100
425 ms187220 KiB
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define iset indexed_set
#define ll long long int
#define ull unsigned long long int
#define f first
#define int ll
#define s second
#define rep(i, st, end) for(int i = st; i < end; i++)
const int mod = 1e9 + 7;
using ii = pair<int, int>;

int sum = 0;

void sub_sum(vector<int> &d, int pos, int mask, map<int, vector<int>> &mp){
	if(pos == d.size())
	{
		mp[sum].push_back(mask);
		return;
	}

	sum += d[pos];
	sub_sum(d, pos + 1, (mask | (1 << pos)), mp);
	sum -= d[pos];
	sub_sum(d, pos + 1, mask, mp);
}

int dp[22][(1<<20)+5];

int rec(vector<int>&d, vector<int>&e, int pos, int mask, map<int, vector<int>> &mp)
{
	if(pos == e.size()) return 1;

	if(dp[pos][mask] != -1) return dp[pos][mask];

	int ans = 0;

	for(auto j: mp[e[pos]])
	{
		if((j&mask) == 0)
		{
			ans |= rec(d, e, pos + 1, (mask | j), mp);
		}
	}

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

void solve()
{
	int n, m;
	cin >> n >> m;

	vector<int> d(m), e(n);

	for(int i = 0; i<n; i++)
	{
		cin >> e[i];
	}

	for(int j = 0; j<m; j++)
	{
		cin >> d[j];
	}

	map<int, vector<int>> mp;
	sub_sum(d, 0, 0, mp);

	rep(i, 0, n+1)
	{
		rep(j, 0, (1<<m) + 5)
		{
			dp[i][j] = -1;
		}
	}

	int ans = rec(d, e, 0, 0, mp);

	if(ans)
	{
		cout << "YES" << '\n';
	}
	else
	{
		cout << "NO" << '\n';
	}

}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // int t; cin>>t; while(t--)
    solve();
}

Compilation message (stderr)

bank.cpp: In function 'void sub_sum(std::vector<long long int>&, long long int, long long int, std::map<long long int, std::vector<long long int> >&)':
bank.cpp:22:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  if(pos == d.size())
      |     ~~~~^~~~~~~~~~~
bank.cpp: In function 'long long int rec(std::vector<long long int>&, std::vector<long long int>&, long long int, long long int, std::map<long long int, std::vector<long long int> >&)':
bank.cpp:38:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  if(pos == e.size()) return 1;
      |     ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...