#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<vector<int>> g;
vector<pair<int, int>> special;
vector<int> c;
int N, M;
int max_or(int i, int j, int b1, int b2, int b3, int b4){
int maximum = -1e9;
if(!b1 && i && j && j < N-1) maximum = g[i][j] + g[i][j-1] + g[i][j+1] + g[i-1][j];
if(!b2 && i < M-1 && j && j < N-1){
maximum = max(maximum, g[i][j]+g[i][j+1]+g[i][j-1]+g[i+1][j]);
}
if(!b3 && i && i < M-1 && j){
maximum = max(maximum, g[i][j]+g[i-1][j]+g[i+1][j]+g[i][j-1]);
}
if(!b4 && i && i < M-1 && j < N-1){
maximum = max(maximum, g[i][j]+g[i+1][j]+g[i-1][j]+g[i][j+1]);
}
return maximum;
}
ll dp(int k, int b1, int b2, int b3, int b4){
if(k==c.size()-1){
return max_or(c[k], special[0].first, b1, b2, b3, b4);
}
else{
ll c1=-1e9, c2=-1e9, c3=-1e9, c4=-1e9;
int j = c[k], i=special[0].first;
if(!b1 && i && j && j < N-1) c1 = g[i][j] + g[i][j-1] + g[i][j+1] + g[i-1][j];
if(!b2 && i < M-1 && j && j < N-1){
c2 = g[i][j]+g[i][j+1]+g[i][j-1]+g[i+1][j];
}
if(!b3 && i && i < M-1 && j){
c3 = g[i][j]+g[i-1][j]+g[i+1][j]+g[i][j-1];
}
if(!b4 && i && i < M-1 && j < N-1){
c4 = g[i][j]+g[i+1][j]+g[i-1][j]+g[i][j+1];
}
if(c[k+1] == i+1)
return dp(k+1, 1, 1, 1, 0) + c3;
if(c[k+1] = i+2){
ll ch1 = max(c1, max(c2, c4)) + dp(k+1, 1, 1, 1, 0);
ll ch2 = c3 + dp(k+1, 0, 0, 0, 0);
return max(ch1, ch2);
}
return max(c1, max(c2, max(c3, c4))) + dp(k+1, 0, 0, 0, 0);
}
}
int main()
{
scanf("%d%d", &M, &N);
g.resize(M, vector<int>(N));
for(int i=0; i < M; i++){
for(int j=0; j < N; j++) scanf("%d", &g[i][j]);
}
int k;
scanf("%d", &k);
bool same_row=true, all_far=true;
special.resize(k);
for(int i=0; i < k; i++){
scanf("%d%d", &special[i].first, &special[i].second);
if(i && special[i].first != special[i-1].first) same_row=false;
if(i && fabs(special[i].first-special[i-1].first) <= 2 && fabs(special[i].second-special[i-1].second) <= 2)
all_far = false;
}
if(all_far){
bool valid=true;
int sum=0;
for(int i=0; i < k; i++){
int m = max_or(special[i].first, special[i].second, 0,0,0,0);
if(m==-1e9){
valid = false;
break;
}
sum += m;
}
if(valid) printf("%d\n", sum);
else printf("No\n");
}
else if(same_row){
c.resize(k);
for(int i=0; i < k; i++) c[i] = special[i].second;
sort(c.begin(), c.end());
ll ans = dp(0, 0, 0, 0, 0);
if(ans < 0) printf("No\n");
else printf("%lld\n", ans);
}
}
Compilation message
covering.cpp: In function 'll dp(int, int, int, int, int)':
covering.cpp:30:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | if(k==c.size()-1){
| ~^~~~~~~~~~~~
covering.cpp:50:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
50 | if(c[k+1] = i+2){
covering.cpp: In function 'int main()':
covering.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d%d", &M, &N);
| ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:64:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | for(int j=0; j < N; j++) scanf("%d", &g[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
covering.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d%d", &special[i].first, &special[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 4 |
Correct |
31 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
62 ms |
8012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
872 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 4 |
Correct |
31 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
62 ms |
8012 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 4 |
Correct |
31 ms |
2904 KB |
Output is correct |
| 5 |
Correct |
62 ms |
8012 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
