Submission #742785

#	Time	Username	Problem	Language	Result	Execution time	Memory
742785		ToniB	Furniture (JOI20_furniture)	C++17	0 / 100	22 ms	26084 KiB

furniture

#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];
		}
	}
	cin >> q;
	for(int i = 1; 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 = 1; i <= q; ++i){
		cout << !ans[i] << "\n";
	}
	return 0;
}

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