#include <bits/stdc++.h>
using namespace std;
void place(long long x, long long y, vector<vector<long long>> &special, long long &p, vector<long long> &depX, vector<long long> &depY, long long N, long long M, long long &tot, vector<vector<long long>> &Tab, long long &minn, int px, int py)
{
if (special[x][y] == 2)
return;
if (special[x][y] == 3)
{
p = 0;
return;
}
tot += Tab[x][y];
long long choose = -1;
for (long long j = 0; j < 4; j++)
{
if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M)
{
if (choose != -1)
p = 0;
choose = j;
}
else
{
minn = min(minn, Tab[x + depX[j]][y + depY[j]]);
tot += Tab[x + depX[j]][y + depY[j]];
if (special[x + depX[j]][y + depY[j]] > 0)
{
if (choose != -1)
p = 0;
choose = j;
}
}
}
for (long long j = 4; j < 8; j++)
{
if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M)
continue;
if (special[x + depX[j]][y + depY[j]] == 1)
{
if (choose != -1)
p = 0;
choose = j - 4;
}
}
if (p == 0)
return;
for (long long j = 0; j < 4; j++)
{
if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M)
continue;
if (j == choose)
{
tot -= Tab[x + depX[j]][y + depY[j]];
}
else if (choose != -1)
special[x + depX[j]][y + depY[j]] = 3;
}
special[x][y] = 2;
if (choose != -1)
return;
special[x][y] = 4;
for (long long j = 8; j < 12; j++)
{
if (x + depX[j] < 0 || x + depX[j] >= N || y + depY[j] < 0 || y + depY[j] >= M)
continue;
if (x + depX[j] == px && y + depY[j] == py)
continue;
if (special[x + depX[j]][y + depY[j]] == 1)
{
place(x + depX[j], y + depY[j], special, p, depX, depY, N, M, tot, Tab, minn, x, y);
tot -= Tab[x + depX[j - 8]][y + depY[j - 8]];
}
if (special[x + depX[j]][y + depY[j]] == 4)
{
tot -= Tab[x + depX[j - 8]][y + depY[j - 8]];
for (long long k = 0; k < 4; k++)
{
if (x + depX[k] < 0 || x + depX[k] >= N || y + depY[k] < 0 || y + depY[k] >= M)
continue;
if (k != j - 8)
special[x + depX[k]][y + depY[k]] = 3;
}
}
if (special[x + depX[j - 8]][y + depY[j - 8]] == 3)
{
for (long long k = 0; k < 4; k++)
{
if (x + depX[k] < 0 || x + depX[k] >= N || y + depY[k] < 0 || y + depY[k] >= M)
continue;
special[x + depX[k]][y + depY[k]] = 3;
}
special[x][y] = 2;
return;
}
}
special[x][y] = 2;
if (choose == -1 && x == px && y == py)
tot -= minn;
}
int main()
{
long long N, M;
cin >> N >> M;
vector<vector<long long>> Tab(N, vector<long long>(M));
for (long long i = 0; i < N; i++)
{
for (long long j = 0; j < M; j++)
{
cin >> Tab[i][j];
}
}
long long K;
cin >> K;
vector<vector<long long>> special(N, vector<long long>(M));
vector<pair<long long, long long>> S;
for (long long i = 0; i < K; i++)
{
long long a, b;
cin >> a >> b;
S.push_back({a, b});
special[a][b] = 1;
}
long long p = 1, tot = 0;
vector<long long> depX = {0, -1, 0, 1, -1, -1, 1, 1, 0, -2, 0, 2}, depY = {-1, 0, 1, 0, -1, 1, 1, -1, -2, 0, 2, 0};
for (long long i = 0; i < K; i++)
{
long long x = S[i].first;
long long y = S[i].second;
long long minn = 1000000;
place(x, y, special, p, depX, depY, N, M, tot, Tab, minn, x, y);
if (p == 0)
break;
}
if (p)
cout << tot;
else
cout << "No";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
856 KB |
Output is correct |
3 |
Correct |
16 ms |
1880 KB |
Output is correct |
4 |
Correct |
50 ms |
5096 KB |
Output is correct |
5 |
Correct |
147 ms |
15964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
6 ms |
856 KB |
Output is correct |
3 |
Correct |
17 ms |
1880 KB |
Output is correct |
4 |
Correct |
48 ms |
5348 KB |
Output is correct |
5 |
Correct |
158 ms |
15964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
600 KB |
Output is correct |
2 |
Correct |
6 ms |
860 KB |
Output is correct |
3 |
Correct |
16 ms |
1992 KB |
Output is correct |
4 |
Correct |
48 ms |
5096 KB |
Output is correct |
5 |
Correct |
151 ms |
15960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
8 ms |
1116 KB |
Output is correct |
4 |
Correct |
5 ms |
860 KB |
Output is correct |
5 |
Correct |
17 ms |
2136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
856 KB |
Output is correct |
3 |
Correct |
16 ms |
1880 KB |
Output is correct |
4 |
Correct |
50 ms |
5096 KB |
Output is correct |
5 |
Correct |
147 ms |
15964 KB |
Output is correct |
6 |
Correct |
2 ms |
344 KB |
Output is correct |
7 |
Correct |
6 ms |
856 KB |
Output is correct |
8 |
Correct |
17 ms |
1880 KB |
Output is correct |
9 |
Correct |
48 ms |
5348 KB |
Output is correct |
10 |
Correct |
158 ms |
15964 KB |
Output is correct |
11 |
Correct |
3 ms |
600 KB |
Output is correct |
12 |
Correct |
6 ms |
860 KB |
Output is correct |
13 |
Correct |
16 ms |
1992 KB |
Output is correct |
14 |
Correct |
48 ms |
5096 KB |
Output is correct |
15 |
Correct |
151 ms |
15960 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
8 ms |
1116 KB |
Output is correct |
19 |
Correct |
5 ms |
860 KB |
Output is correct |
20 |
Correct |
17 ms |
2136 KB |
Output is correct |
21 |
Correct |
2 ms |
600 KB |
Output is correct |
22 |
Correct |
5 ms |
856 KB |
Output is correct |
23 |
Correct |
19 ms |
1880 KB |
Output is correct |
24 |
Correct |
50 ms |
5100 KB |
Output is correct |
25 |
Correct |
155 ms |
15960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
856 KB |
Output is correct |
3 |
Correct |
16 ms |
1880 KB |
Output is correct |
4 |
Correct |
50 ms |
5096 KB |
Output is correct |
5 |
Correct |
147 ms |
15964 KB |
Output is correct |
6 |
Correct |
2 ms |
344 KB |
Output is correct |
7 |
Correct |
6 ms |
856 KB |
Output is correct |
8 |
Correct |
17 ms |
1880 KB |
Output is correct |
9 |
Correct |
48 ms |
5348 KB |
Output is correct |
10 |
Correct |
158 ms |
15964 KB |
Output is correct |
11 |
Correct |
3 ms |
600 KB |
Output is correct |
12 |
Correct |
6 ms |
860 KB |
Output is correct |
13 |
Correct |
16 ms |
1992 KB |
Output is correct |
14 |
Correct |
48 ms |
5096 KB |
Output is correct |
15 |
Correct |
151 ms |
15960 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
8 ms |
1116 KB |
Output is correct |
19 |
Correct |
5 ms |
860 KB |
Output is correct |
20 |
Correct |
17 ms |
2136 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
432 KB |
Output is correct |
26 |
Correct |
2 ms |
600 KB |
Output is correct |
27 |
Correct |
5 ms |
856 KB |
Output is correct |
28 |
Correct |
19 ms |
1880 KB |
Output is correct |
29 |
Correct |
50 ms |
5100 KB |
Output is correct |
30 |
Correct |
155 ms |
15960 KB |
Output is correct |
31 |
Correct |
234 ms |
32532 KB |
Output is correct |
32 |
Correct |
178 ms |
20988 KB |
Output is correct |
33 |
Correct |
184 ms |
22908 KB |
Output is correct |
34 |
Correct |
168 ms |
20644 KB |
Output is correct |
35 |
Correct |
196 ms |
28344 KB |
Output is correct |