oj.uz

Submission #684458

# Submission time Handle Problem Language Result Execution time Memory
684458 2023-01-21T09:47:48 Z GudStonks Bank (IZhO14_bank) C++17
0 / 100
 76 ms 205496 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9+7;
ll n, m, arr[25], brr[25], dp[25][(1<<20)];
vector<ll>ms[25];

ll rec(ll i, ll mask){
	if(i == 0)
		return dp[i][mask] = 1;
	if(dp[i][mask] != -1)
		return dp[i][mask];
	dp[i][mask] = 0;
	for(auto it : ms[i]){
		if((mask & it) == it)
			dp[i][mask] |= rec(i - 1, mask - it);
	}
	return dp[i][mask];
}

void fun(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++)cin>>arr[i];
	for(int i = 1; i <= m; i++)cin>>brr[i];
	for(int i = 1; i < (1 << m); i++){
		ll sum = 0;
		for(int j = 0; (1 << j) <= i; j++)
			if(i & j)
				sum += brr[j + 1];
		for(int j = 1; j <= n; j++)
			if(sum == arr[j])
				ms[j].push_back(i);
	}
	memset(dp, -1, sizeof(dp));
	cout<<(rec(n, (1 << m) - 1) == 1 ? "YES\n" : "NO\n");
}
int  main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int ttt = 1;
	//cin>>ttt;
	while(ttt--)fun();
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 205388 KB Output is correct
2 Correct 75 ms 205444 KB Output is correct
3 Incorrect 76 ms 205380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 205392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 205496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 205388 KB Output is correct
2 Correct 75 ms 205444 KB Output is correct
3 Incorrect 76 ms 205380 KB Output isn't correct
4 Halted 0 ms 0 KB -