Submission #1129024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129024		Agageldi	Plus Minus (BOI17_plusminus)	C++17	0 / 100	1095 ms	320 KiB

plusminus

/*
ID: agageld1
LANG: C++17
TASK:
*/
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 400005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define rep(c, a, b) for(c = a; c <= b; c++)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int c[] = {0,0,-1,-1};
int d[] = {0,-1,0,-1};
ll n, t, vis[3000][3000], m, k, ans;
char p, a[5000][5000], b[] = {'+','-'};
map <char,int> vip;

bool check() {
	for(int i = 2; i <= n; i++) {
		for(int j = 2; j <= m; j++) {
			vip.clear();
			for(int l = 0; l < 4; l++) {
				if(a[i + c[l]][j + d[l]] == '1') return 0;
				vip[a[i + c[l]][j + d[l]]]++;
			}
			if(vip['+'] != vip['-']) return 0;
		}
	}
	return 1;
}

void solve(int x,int y) {
	if(x > n || y > m || x == 0 || y == 0 || vis[x][y] == 1) return;
	char l = a[x][y];
	if(x == n && y == m) {
		for(int i = 0; i <= 1; i++) {
			if(l == '1') a[x][y] = b[i];
			if(check())	ans++;
			if(l != '1') break;
		}
		a[x][y] = l;
		return;
	}
	vis[x][y] = 1;
	for(int i = 0; i <= 1; i++) {
		if(l == '1') a[x][y] = b[i];
		solve(x+1,y);
		solve(x,y+1);
		solve(x,y-1);
		solve(x-1,y);
		if(l != '1') break;
	}
	vis[x][y] = 0;
	a[x][y] = l;
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 1;i<=n;i++) {
		for(int j =1;j<=m;j++) {
			a[i][j] = '1';
		}
	}
	for(int i = 1; i <= k; i++) {
		int x, y;
		cin >> p >> x >> y;
		a[x][y] = p;
	}
	solve(1,1);
	cout << ans / 3 << '\n';
}

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