Submission #865044

#	Time	Username	Problem	Language	Result	Execution time	Memory
865044		maks007	Plus Minus (BOI17_plusminus)	C++14	12 / 100	762 ms	980 KiB

plusminus

// Bismi ALlah
#include "bits/stdc++.h"

using namespace std;

const int mod = (int)1e9 + 7;

int check(int a, int b, int m) {
	for(int i = 1; i < m; i ++) {
		vector <int> cnt(2, 0);
		cnt[(a & (1 << i)) > 0] ++;
		cnt[(b & (1 << i)) > 0] ++;
		cnt[(a & (1 << (i - 1))) > 0] ++;
		cnt[(b & (1 << (i - 1))) > 0] ++;
		if(cnt[0] == cnt[1]) continue;
		return 0;
	}
	return 1;
}

signed main () {
	int n, m;
	cin >> n >> m;
	int dp[n][(1 << m)], k;
	memset(dp, 0, sizeof(dp));
	cin >> k;
	map <pair <int,int>,int> setle;
	for(;k>=1;k--) {
		char ch;
		cin >> ch;
		int i, j;
		cin >> i >> j;
		i --, j --;
		if(ch == '-') setle[{i, j}] = 0;
		else setle[{i, j}] = 1;
	}
	for(int i = 0; i < n; i ++) {
		for(int mask = 0; mask < (1 << m); mask ++) {
			for(auto j : setle) {
				if(j.first.first == i) {
					if((((mask & (1 << j.first.second)) > 0) == j.second)) continue;
					goto end;
				}
			}
			if(i == 0) dp[i][mask] = 1;
			else {
				for(int mask2 = 0; mask2 < (1 << m); mask2 ++) {
					if(check(mask, mask2, m)) dp[i][mask] += dp[i-1][mask2], dp[i][mask] %= mod;
				}
			}
			//cout << i << " " << mask << " " << dp[i][mask] << "\n";
			end:;
		}
	}
//	cout << check(3, 0, 2) << "<-\n";
	int ans = 0;
	for(int i=0; i < (1 << m); i ++) ans += dp[n-1][i], ans %= mod;
	cout << ans;
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 42
• Subtask 3: 0 / 46