Submission #683833

#	Time	Username	Problem	Language	Result	Execution time	Memory
683833		abc864197532	Furniture (JOI20_furniture)	C++17	5 / 100	5083 ms	2432 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m, q;
	cin >> n >> m;
	vector <vector <bool>> is(n, vector <bool>(m, false));
	for (int i = 0; i < n; ++i) {
		for (int j = 0, x; j < m; ++j) {
			cin >> x, is[i][j] = x;
		}
	}
	vector <vector <bool>> dp(n, vector <bool>(m, false));
	auto chk = [&]() {
		dp.assign(n, vector <bool>(m, false));
		dp[0][0] = true;
		for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (dp[i][j]) {
			if (i + 1 < n && !is[i + 1][j]) {
				dp[i + 1][j] = true;
			}
			if (j + 1 < m && !is[i][j + 1]) {
				dp[i][j + 1] = true;
			}
		}
	};
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y, --x, --y;
		is[x][y] = true;
		chk();
		if (dp[n - 1][m - 1]) {
			cout << "1\n";
		} else {
			cout << "0\n";
			is[x][y] = false;
		}
	}
}

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