Submission #742782

# Submission time Handle Problem Language Result Execution time Memory
742782 2023-05-16T23:23:28 Z ToniB Furniture (JOI20_furniture) C++17
0 / 100
20 ms 26068 KB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1001;

int n, m, q, xq[MAXN], yq[MAXN], val[MAXN][MAXN];
vector<int> dp[MAXN][MAXN];
bool flag[MAXN][MAXN], ans[MAXN * MAXN];

vector<int> better(vector<int> a, vector<int> b){
	if(a.empty()) swap(a, b);
	if(b.empty()) return a;
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	for(int i = 0; i < (int)a.size(); ++i){
		if(a[i] > b[i]) return a;
		if(a[i] < b[i]) return b;
	}
	return a;
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			cin >> flag[i][j];
			val[i][j] = n*m;
		}
	}
	cin >> q;
	for(int i = 0; i < q; ++i){
		cin >> xq[i] >> yq[i], --xq[i], --yq[i];
		val[xq[i]][yq[i]] = i;
	}
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			if(i == 0 && j == 0){
				dp[i][j] = {val[i][j]};
				continue;
			}
			if(flag[i][j]) continue;
			vector<int> down, right;
			if(i && !dp[i - 1][j].empty()){
				down = dp[i - 1][j];
			}
			if(j && !dp[i][j - 1].empty()){
				right = dp[i][j - 1];
			}
			vector<int> opt = better(down, right);
			if(!opt.empty()){
				opt.push_back(val[i][j]);
				dp[i][j] = opt;
			}
		}
	}
	for(int x : dp[n - 1][m - 1]){
		ans[x] = 1;
	}
	for(int i = 0; i < q; ++i){
		cout << !ans[i] << "\n";
	}
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 20 ms 26068 KB Output is correct
2 Incorrect 16 ms 25008 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 20 ms 26068 KB Output is correct
2 Incorrect 16 ms 25008 KB Output isn't correct
3 Halted 0 ms 0 KB -