#include<bits/stdc++.h>
using namespace std;
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, 1, 0, -1};
const int INF = 1e9 + 5;
int n, m;
bool check(int i, int j)
{
return i >= 0 && i < n && j >= 0 && j < m;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin >> a[i][j];
}
}
vector<vector<bool>> used(n, vector<bool>(m, 0));
int k;
cin >> k;
set<int> s;
for (int _ = 0; _ < k; ++_)
{
int r, c;
cin >> r >> c;
used[r][c] = 1;
s.insert(r);
}
if (s.size() == 1)
{
int r = *s.begin();
vector<pair<int, int>> t;
for (int i = 0; i < m; ++i)
{
if (used[r][i])
{
t.emplace_back(r, i);
}
}
vector<vector<int>> dp(k, vector<int>(4, -INF));
for (int h = 0; h < 4; ++h)
{
bool fl = 1;
int sum = a[t[0].first][t[0].second];
for (int h2 = 0; h2 < 4; ++h2)
{
if (h != h2)
{
int x = t[0].first + DX[h2], y = t[0].second + DY[h2];
if (!check(x, y))
{
fl = 0;
break;
}
sum += a[x][y];
}
}
if (fl)
{
dp[0][h] = sum;
}
}
for (int i = 1; i < k; ++i)
{
for (int h = 0; h < 4; ++h)
{
bool fl = 1;
int sum = a[t[i].first][t[i].second];
for (int h2 = 0; h2 < 4; ++h2)
{
if (h != h2)
{
int x = t[i].first + DX[h2], y = t[i].second + DY[h2];
if (!check(x, y))
{
fl = 0;
break;
}
sum += a[x][y];
}
}
if (fl)
{
for (int p = 0; p < 4; ++p)
{
if (dp[i - 1][p] != -INF)
{
bool fl2 = 1;
for (int h2 = 0; h2 < 4; ++h2)
{
if (h2 != h)
{
for (int p2 = 0; p2 < 4; ++p2)
{
if (p2 != p)
{
if (t[i].first + DX[h2] == t[i - 1].first + DX[p2] && t[i].second + DY[h2] == t[i - 1].second + DY[p2])
{
fl2 = 0;
break;
}
}
}
}
}
if (fl2)
{
dp[i][h] = max(dp[i][h], dp[i - 1][p] + sum);
}
}
}
}
}
}
int ans = -INF;
for (int i = 0; i < 4; ++i)
{
ans = max(ans, dp[k - 1][i]);
}
if (ans == -INF)
{
cout << "No\n";
}
else
{
cout << ans;
}
return 0;
}
vector<vector<int>> go(n, vector<int>(m, -1));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (used[i][j])
{
for (int h = 0; h < 4; ++h)
{
int x = i + DX[h], y = j + DY[h];
if (check(x, y) && used[x][y])
{
go[i][j] = h;
go[x][y] = h ^ 2;
}
}
}
}
}
vector<vector<int>> cnt(n, vector<int>(m, 0));
int ans = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (!used[i][j])
{
continue;
}
if (go[i][j] == -1)
{
int mx = -INF;
for (int h = 0; h < 4; ++h)
{
int sum = a[i][j];
bool fl = 1;
for (int h2 = 0; h2 < 4; ++h2)
{
if (h2 != h)
{
int x = i + DX[h2], y = j + DY[h2];
if (!check(x, y))
{
fl = 0;
break;
}
sum += a[x][y];
}
}
if (fl)
{
mx = max(mx, sum);
}
}
if (mx == -INF)
{
cout << "No\n";
return 0;
}
ans += mx;
}
else
{
bool fl = 1;
int sum = a[i][j];
++cnt[i][j];
for (int h = 0; h < 4; ++h)
{
if (h != go[i][j])
{
int x = i + DX[h], y = j + DY[h];
if (!check(x, y))
{
fl = 0;
break;
}
sum += a[x][y];
++cnt[x][y];
}
}
if (!fl)
{
cout << "No\n";
return 0;
}
ans += sum;
}
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (cnt[i][j] >= 2)
{
cout << "No\n";
return 0;
}
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
768 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
28 ms |
3968 KB |
Output is correct |
| 5 |
Correct |
85 ms |
12408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
768 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
30 ms |
4096 KB |
Output is correct |
| 5 |
Correct |
84 ms |
12408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
8 ms |
768 KB |
Output is correct |
| 4 |
Correct |
8 ms |
640 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
768 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
28 ms |
3968 KB |
Output is correct |
| 5 |
Correct |
85 ms |
12408 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
7 ms |
768 KB |
Output is correct |
| 8 |
Correct |
12 ms |
1536 KB |
Output is correct |
| 9 |
Correct |
30 ms |
4096 KB |
Output is correct |
| 10 |
Correct |
84 ms |
12408 KB |
Output is correct |
| 11 |
Correct |
5 ms |
512 KB |
Output is correct |
| 12 |
Incorrect |
7 ms |
768 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
768 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1536 KB |
Output is correct |
| 4 |
Correct |
28 ms |
3968 KB |
Output is correct |
| 5 |
Correct |
85 ms |
12408 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
7 ms |
768 KB |
Output is correct |
| 8 |
Correct |
12 ms |
1536 KB |
Output is correct |
| 9 |
Correct |
30 ms |
4096 KB |
Output is correct |
| 10 |
Correct |
84 ms |
12408 KB |
Output is correct |
| 11 |
Correct |
5 ms |
512 KB |
Output is correct |
| 12 |
Incorrect |
7 ms |
768 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
