Submission #529095

#	Time	Username	Problem	Language	Result	Execution time	Memory
529095		d2k05	Furniture (JOI20_furniture)	C++14	0 / 100	14 ms	716 KiB

furniture

#include <bits/stdc++.h>

#define fastio ios_base :: sync_with_stdio(0), cin.tie(0);

using namespace std;
using ll = long long;

const int mxN = 1e3 + 5, mod = 1e9 + 7;

int n, m, a[mxN][mxN];
bool dp[mxN][mxN], s[mxN][mxN];

int main() {
	fastio;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) cin >> a[i][j];
	}
	dp[1][1] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1 + (i == 1); j <= m; ++j) {
			dp[i][j] = 0;
			if (a[i][j]) continue;
			dp[i][j] = (dp[i - 1][j] | dp[i][j - 1]);
		}
	}
	s[n][m] = 1;
	for (int i = n; i > 0; i--) {
		for (int j = m - (i == n); j > 0; j--) {
			s[i][j] = 0;
			if (a[i][j]) continue;
			s[i][j] = (s[i + 1][j] | s[i][j + 1]);
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		if ((dp[x + 1][y - 1] & s[x + 1][y - 1]) || (dp[x - 1][y + 1] & s[x - 1][y + 1])) {
			a[x][y] = 1;
			cout << "1\n";
			dp[1][1] = 1;
			for (int i = 1; i <= n; ++i) {
				for (int j = 1 + (i == 1); j <= m; ++j) {
					dp[i][j] = 0;
					if (a[i][j]) continue;
					dp[i][j] = (dp[i - 1][j] | dp[i][j - 1]);
				}
			}
			s[n][m] = 1;
			for (int i = n; i > 0; i--) {
				for (int j = m - (i == n); j > 0; j--) {
					s[i][j] = 0;
					if (a[i][j]) continue;
					s[i][j] = (s[i + 1][j] | s[i][j + 1]);
				}
			}
		}
		else
			cout << "0\n";
	}
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95