#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
vector<vector<int>> g;
vector<pair<int, int>> special;
vector<int> c;
int N, M;
int memo[1001][2][2][2][2];
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){
//cout << max_or(c[k], special[0].first, b1, b2, b3, b4) << endl;
return max_or(special[0].first, c[k], b1, b2, b3, b4);
}
if(memo[k][b1][b2][b3][b4] != -1) return memo[k][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];
}
//cout << c1 <<" "<< c2 <<" "<< c3 <<" "<< c4;
if(c[k+1] == j+1)
return memo[k][b1][b2][b3][b4] = dp(k+1, 1, 1, 1, 0) + c3;
if(c[k+1] = j+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 memo[k][b1][b2][b3][b4] = max(ch1, ch2);
}
return memo[k][b1][b2][b3][b4] = 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());
memset(memo, -1, sizeof memo);
ll ans = dp(0, 0, 0, 0, 0);
if(ans < 0) printf("No\n");
else printf("%lld\n", ans);
}
}
Compilation message
adventure.cpp: In function 'll dp(int, int, int, int, int)':
adventure.cpp:32:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | if(k==c.size()-1){
| ~^~~~~~~~~~~~
adventure.cpp:54:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
54 | if(c[k+1] = j+2){
adventure.cpp: In function 'int main()':
adventure.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d%d", &M, &N);
| ~~~~~^~~~~~~~~~~~~~~~
adventure.cpp:68:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | for(int j=0; j < N; j++) scanf("%d", &g[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
adventure.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d", &k);
| ~~~~~^~~~~~~~~~
adventure.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d%d", &special[i].first, &special[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
498 ms |
97916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
498 ms |
97916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
102400 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
498 ms |
97916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
