oj.uz

Submission #529093

# Submission time Handle Problem Language Result Execution time Memory
529093 2022-02-22T06:13:27 Z d2k05 Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 1040 KB 
#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];
	}
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		a[x][y] = 1;
		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]);
			}
		}
		if (dp[n][m] && s[1][1]) 
			cout << "1\n";
		else
			a[x][y] = 0, cout << "0\n";
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 844 KB Output is correct
2 Correct 80 ms 1028 KB Output is correct
3 Correct 179 ms 852 KB Output is correct
4 Correct 406 ms 872 KB Output is correct
5 Correct 437 ms 916 KB Output is correct
6 Correct 547 ms 1028 KB Output is correct
7 Correct 343 ms 912 KB Output is correct
8 Correct 365 ms 1040 KB Output is correct
9 Correct 275 ms 924 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 844 KB Output is correct
2 Correct 80 ms 1028 KB Output is correct
3 Correct 179 ms 852 KB Output is correct
4 Correct 406 ms 872 KB Output is correct
5 Correct 437 ms 916 KB Output is correct
6 Correct 547 ms 1028 KB Output is correct
7 Correct 343 ms 912 KB Output is correct
8 Correct 365 ms 1040 KB Output is correct
9 Correct 275 ms 924 KB Output is correct
10 Execution timed out 5044 ms 816 KB Time limit exceeded
11 Halted 0 ms 0 KB -