oj.uz

Submission #337829

# Submission time Handle Problem Language Result Execution time Memory
337829 2020-12-21T20:26:10 Z Tosic Divide and conquer (IZhO14_divide) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
#define maxA 1010
#define maxn 21
using namespace std;

int n, m, a[maxn],b[maxn], ans;
vector<vector<int> > allMasks;
int dp[maxn][1<<20];

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
	}
	for(int i = 0; i < m; ++i){
		cin >> b[i];
	}
	allMasks.resize(maxA, vector<int>());
	for(int i = 0; i < (1<<m); ++i){
		int tmp = 0;
		for(int j = 0; j < m; ++j){
			tmp += ((i>>j) & 1)*b[j];
		}
		if(tmp < maxA){
			allMasks[tmp].push_back(i);
		}
	}
	for(int i = 0; i < n; ++i){
		if(i == 0){
			for(auto j:allMasks[a[i]]){
				dp[i][j] = 1;
			}
			continue;
		}
		for(int mask = 0; mask < (1<<m); ++mask){
			for(auto x : allMasks[a[i]]){
                //cerr << x << ' ';
				if(((x & mask) == x) and dp[i-1][mask^x]){
					dp[i][mask] = 1;
					//cerr << i << ' ' << mask << '\n';
					break;
				}
			}
		}
	}
	for(int i = 0; i < (1<<m); ++i){
		ans |=dp[n-1][i];
	}
	if(ans){
		cout<<"YES\n";
	} else {
		cout << "NO\n";
	}
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 52.0

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