#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;
int r, c;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0,-1, 1};
vector<vector<int>> a, dp[2], col;
queue<pair<int,int>> q;
bool ok(int i, int j) {
return i >= 1 && i <= r && j >= 1 && j <= c;
}
void place(int i, int j, int k) {
// clog << i << ' ' << j << ' ' << k << '\n';
for (int p = 0; p < 4; p++)
if (p != k) {
int x = i + dx[p], y = j + dy[p];
if (!ok(x, y) || col[x][y])
cout << "No", exit(0);
q.push({x, y});
col[x][y] = 2;
}
col[i][j] = 2;
}
void bfs() {
while (!q.empty()) {
int i, j; tie(i, j) = q.front(); q.pop();
for (int p = 0; p < 4; p++) {
int x = i + dx[p], y = j + dy[p];
if (ok(x, y) && abs(col[x][y]) == 1) {
// if (x == 4 && y == 5) clog << "ok";
place(x, y, p ^ 1);
col[x][y] = 2;
}
}
}
}
void dfs(int i, int j, int k) {
col[i][j] = -1;
dp[0][i][j] = dp[1][i][j] = -INF;
for (int p = 0; p < 4; p++) if (k != p) {
int x = i + 2 * dx[p], y = j + 2 * dy[p];
if (!ok(x, y)) continue;
if (col[x][y] == -1) {
place(i, j, p), bfs();
return;
}
else if (col[x][y] == 1)
dfs(x, y, p ^ 1);
}
for (int p = 0; p < 4; p++) {
int res = a[i][j];
for (int d = 0; d < 4; d++) {
// if (i == 4 && j == 2 && p == 3) clog << db(res) << db(d) << '\n';
int x = i + 2 * dx[d], y = j + 2 * dy[d];
if (d == p) {
if (ok(x, y) && d != k) {
res += max(dp[0][x][y], dp[1][x][y]);
}
}
else {
res += a[i + dx[d]][j + dy[d]];
if (ok(x, y) && d != k) {
res += dp[0][x][y];
}
}
}
dp[p != k][i][j] = max(dp[p != k][i][j], res);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen(".INP", "r", stdin);
//freopen(".OUT", "w", stdout);
cin >> r >> c;
a.resize(r + 4);
for (int i = 0; i < r + 4; i++)
a[i].resize(c + 4);
dp[0] = dp[1] = col = a;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
cin >> a[i][j];
int k; cin >> k;
for (int i = 1; i <= k; i++) {
int x, y; cin >> x >> y;
x++, y++;
col[x][y] = 1;
q.push({x, y});
}
for (int i = 1; i <= r; i++)
q.push({i, 0}), q.push({i, c + 1});
for (int j = 1; j <= c; j++) {
q.push({0, j}), q.push({r + 1, j});
}
bfs();
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) if (col[i][j] == 1) {
if (i > 1 && j > 1 && col[i - 1][j - 1] == 1) {
place(i, j, 0), bfs();
}
if (i > 1 && j < c && col[i - 1][j + 1] == 1)
place(i, j, 0), bfs();
}
int res = 0;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) if (col[i][j] == 1) {
dfs(i, j, -1);
if (col[i][j] == -1) {
res += dp[1][i][j];
// clog << dp[1][i][j];
}
}
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
if (col[i][j] == 2)
res += a[i][j];
cout << res;
// for (int i = 1; i <= r; i++)
// for (int j = 1; j <= c; j++)
// cout << col[i][j] << (j == c ? '\n' : ' ');
// clog << a[6][2];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
852 KB |
Output is correct |
3 |
Correct |
9 ms |
2004 KB |
Output is correct |
4 |
Correct |
22 ms |
5240 KB |
Output is correct |
5 |
Correct |
71 ms |
16320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
11 ms |
2008 KB |
Output is correct |
4 |
Correct |
20 ms |
5248 KB |
Output is correct |
5 |
Correct |
80 ms |
16292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
448 KB |
Output is correct |
2 |
Correct |
3 ms |
852 KB |
Output is correct |
3 |
Correct |
7 ms |
2004 KB |
Output is correct |
4 |
Correct |
26 ms |
5204 KB |
Output is correct |
5 |
Correct |
82 ms |
16276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
5 ms |
1492 KB |
Output is correct |
4 |
Correct |
3 ms |
1108 KB |
Output is correct |
5 |
Correct |
9 ms |
2712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
1 ms |
324 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
852 KB |
Output is correct |
3 |
Correct |
9 ms |
2004 KB |
Output is correct |
4 |
Correct |
22 ms |
5240 KB |
Output is correct |
5 |
Correct |
71 ms |
16320 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
11 ms |
2008 KB |
Output is correct |
9 |
Correct |
20 ms |
5248 KB |
Output is correct |
10 |
Correct |
80 ms |
16292 KB |
Output is correct |
11 |
Correct |
1 ms |
448 KB |
Output is correct |
12 |
Correct |
3 ms |
852 KB |
Output is correct |
13 |
Correct |
7 ms |
2004 KB |
Output is correct |
14 |
Correct |
26 ms |
5204 KB |
Output is correct |
15 |
Correct |
82 ms |
16276 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
5 ms |
1492 KB |
Output is correct |
19 |
Correct |
3 ms |
1108 KB |
Output is correct |
20 |
Correct |
9 ms |
2712 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
3 ms |
932 KB |
Output is correct |
23 |
Correct |
7 ms |
2004 KB |
Output is correct |
24 |
Correct |
20 ms |
5280 KB |
Output is correct |
25 |
Correct |
66 ms |
16308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
852 KB |
Output is correct |
3 |
Correct |
9 ms |
2004 KB |
Output is correct |
4 |
Correct |
22 ms |
5240 KB |
Output is correct |
5 |
Correct |
71 ms |
16320 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
852 KB |
Output is correct |
8 |
Correct |
11 ms |
2008 KB |
Output is correct |
9 |
Correct |
20 ms |
5248 KB |
Output is correct |
10 |
Correct |
80 ms |
16292 KB |
Output is correct |
11 |
Correct |
1 ms |
448 KB |
Output is correct |
12 |
Correct |
3 ms |
852 KB |
Output is correct |
13 |
Correct |
7 ms |
2004 KB |
Output is correct |
14 |
Correct |
26 ms |
5204 KB |
Output is correct |
15 |
Correct |
82 ms |
16276 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
5 ms |
1492 KB |
Output is correct |
19 |
Correct |
3 ms |
1108 KB |
Output is correct |
20 |
Correct |
9 ms |
2712 KB |
Output is correct |
21 |
Correct |
1 ms |
320 KB |
Output is correct |
22 |
Correct |
1 ms |
324 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
2 ms |
468 KB |
Output is correct |
27 |
Correct |
3 ms |
932 KB |
Output is correct |
28 |
Correct |
7 ms |
2004 KB |
Output is correct |
29 |
Correct |
20 ms |
5280 KB |
Output is correct |
30 |
Correct |
66 ms |
16308 KB |
Output is correct |
31 |
Correct |
121 ms |
26792 KB |
Output is correct |
32 |
Correct |
63 ms |
16704 KB |
Output is correct |
33 |
Correct |
73 ms |
21360 KB |
Output is correct |
34 |
Correct |
64 ms |
16692 KB |
Output is correct |
35 |
Correct |
110 ms |
22984 KB |
Output is correct |