oj.uz

답안 #742779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
742779 2023-05-16T23:08:59 Z ToniB Furniture (JOI20_furniture) C++17
0 / 100
 16 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> higher(vector<int> a, vector<int> b){
	if(a.empty()) swap(a, b);
	if(b.empty()) return a;
	for(int i = 0; i < (int)a.size(); ++i){
		if(a[i] < b[i]) return b;
		if(a[i] > b[i]) return a;
	}
	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 = higher(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;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 26068 KB Output is correct
2 Incorrect 15 ms 24956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 26068 KB Output is correct
2 Incorrect 15 ms 24956 KB Output isn't correct
3 Halted 0 ms 0 KB -