#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());
assert(a.size() == b.size());
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 |
26056 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
24968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
26056 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
24968 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
