#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
vector<vector<int>> a, grid;
vector<pair<int, int>> sp;
int K, N, M;
int memo[5003][5];
int dp(int i, int prev){
if(i==K) return 0;
if(memo[i][prev] != -1) return memo[i][prev];
int s1=-1, s2=-1, s3=-1, s4=-1;
int x=sp[i].first, y=sp[i].second;
int k=sp[i-1].first, j=sp[i-1].second;
if(prev==1){
grid[k][j]=grid[k-1][j]=grid[k+1][j]=grid[k][j-1]=1;
if(x-1>=0 && x+1<M && y-1>=0 && grid[x-1][y]+grid[x+1][y]+grid[x][y-1]==0){
int p=dp(i+1, 1);
if(p != -1)
s1 = a[x][y]+a[x-1][y]+a[x+1][y]+a[x][y-1]+p;
}
if(x-1>=0 && x+1<M && y+1<N && grid[x-1][y]+grid[x+1][y]+grid[x][y+1]==0){
int p=dp(i+1, 2);
if(p!=-1)
s2 = a[x][y]+a[x-1][y]+a[x+1][y]+a[x][y+1]+p;
}
if(y-1>=0 && y+1<N && x-1>=0 && grid[x][y-1]+grid[x][y+1]+grid[x-1][y]==0){
int p=dp(i+1, 3);
if(p!=-1)
s3 = a[x][y]+a[x][y-1]+a[x][y+1]+a[x-1][y]+p;
}
if(y-1>=0 && y+1<N && x+1<M && grid[x][y-1]+grid[x][y+1]+grid[x+1][y]==0){
int p=dp(i+1, 4);
if(p!=-1)
s4 = p+a[x][y]+a[x][y-1]+a[x][y+1]+a[x+1][y];
}
grid[k][j]=grid[k-1][j]=grid[k+1][j]=grid[k][j-1]=0;
}
if(prev==2){
grid[k][j] = grid[k-1][j]=grid[k+1][j]=grid[k][j+1]=1;
if(x-1>=0 && x+1<M && y-1>=0 && grid[x-1][y]+grid[x+1][y]+grid[x][y-1]==0){
int p=dp(i+1, 1);
if(p != -1)
s1 = a[x][y]+a[x-1][y]+a[x+1][y]+a[x][y-1]+p;
}
if(x-1>=0 && x+1<M && y+1<N && grid[x-1][y]+grid[x+1][y]+grid[x][y+1]==0){
int p=dp(i+1, 2);
if(p!=-1)
s2 = a[x][y]+a[x-1][y]+a[x+1][y]+a[x][y+1]+p;
}
if(y-1>=0 && y+1<N && x-1>=0 && grid[x][y-1]+grid[x][y+1]+grid[x-1][y]==0){
int p=dp(i+1, 3);
if(p!=-1)
s3 = a[x][y]+a[x][y-1]+a[x][y+1]+a[x-1][y]+p;
}
if(y-1>=0 && y+1<N && x+1<M && grid[x][y-1]+grid[x][y+1]+grid[x+1][y]==0){
int p=dp(i+1, 4);
if(p!=-1)
s4 = p+a[x][y]+a[x][y-1]+a[x][y+1]+a[x+1][y];
}
grid[k][j] = grid[k-1][j]=grid[k+1][j]=grid[k][j+1]=0;
}
if(prev==3){
grid[k][j]=grid[k][j-1]=grid[k][j+1]=grid[k-1][j]=1;
if(x-1>=0 && x+1<M && y-1>=0 && grid[x-1][y]+grid[x+1][y]+grid[x][y-1]==0){
int p=dp(i+1, 1);
if(p != -1)
s1 = a[x][y]+a[x-1][y]+a[x+1][y]+a[x][y-1]+p;
}
if(x-1>=0 && x+1<M && y+1<N && grid[x-1][y]+grid[x+1][y]+grid[x][y+1]==0){
int p=dp(i+1, 2);
if(p!=-1)
s2 = a[x][y]+a[x-1][y]+a[x+1][y]+a[x][y+1]+p;
}
if(y-1>=0 && y+1<N && x-1>=0 && grid[x][y-1]+grid[x][y+1]+grid[x-1][y]==0){
int p=dp(i+1, 3);
if(p!=-1)
s3 = a[x][y]+a[x][y-1]+a[x][y+1]+a[x-1][y]+p;
}
if(y-1>=0 && y+1<N && x+1<M && grid[x][y-1]+grid[x][y+1]+grid[x+1][y]==0){
int p=dp(i+1, 4);
if(p!=-1)
s4 = p+a[x][y]+a[x][y-1]+a[x][y+1]+a[x+1][y];
}
grid[k][j]=grid[k][j-1]=grid[k][j+1]=grid[k-1][j]=0;
}
if(prev==4){
grid[k][j]=grid[k][j-1]=grid[k][j+1]=grid[k+1][j]=1;
if(x-1>=0 && x+1<M && y-1>=0 && grid[x-1][y]+grid[x+1][y]+grid[x][y-1]==0){
int p=dp(i+1, 1);
if(p != -1)
s1 = a[x][y]+a[x-1][y]+a[x+1][y]+a[x][y-1]+p;
}
if(x-1>=0 && x+1<M && y+1<N && grid[x-1][y]+grid[x+1][y]+grid[x][y+1]==0){
int p=dp(i+1, 2);
if(p!=-1)
s2 = a[x][y]+a[x-1][y]+a[x+1][y]+a[x][y+1]+p;
}
if(y-1>=0 && y+1<N && x-1>=0 && grid[x][y-1]+grid[x][y+1]+grid[x-1][y]==0){
int p=dp(i+1, 3);
if(p!=-1)
s3 = a[x][y]+a[x][y-1]+a[x][y+1]+a[x-1][y]+p;
}
if(y-1>=0 && y+1<N && x+1<M && grid[x][y-1]+grid[x][y+1]+grid[x+1][y]==0){
int p=dp(i+1, 4);
if(p!=-1)
s4 = p+a[x][y]+a[x][y-1]+a[x][y+1]+a[x+1][y];
}
grid[k][j]=grid[k][j-1]=grid[k][j+1]=grid[k+1][j]=0;
}
int d=max(s1, max(s2, max(s3, s4)));
return memo[i][prev] = d;
}
int f(int x){
if(x==K) return 0;
int i=sp[x].first, j=sp[x].second;
int s1=-1, s2=-1, s3=-1, s4=-1;
if(i-1>=0 && i+1<M && j-1>=0){
if(grid[i][j]+grid[i-1][j]+grid[i+1][j]+grid[i][j-1]==0){
grid[i][j]=grid[i-1][j]=grid[i+1][j]=grid[i][j-1]=1;
int d=f(x+1);
if(d!=-1) s1 = a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j-1]+d;
grid[i][j]=grid[i-1][j]=grid[i+1][j]=grid[i][j-1]=0;
}
}
if(i-1>=0 && i+1<M && j+1<N){
if(grid[i][j]+grid[i-1][j]+grid[i+1][j]+grid[i][j+1]==0){
grid[i][j]=grid[i-1][j]=grid[i+1][j]=grid[i][j+1]=1;
int d=f(x+1);
if(d!=-1) s2 = a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j+1]+d;
grid[i][j]=grid[i-1][j]=grid[i+1][j]=grid[i][j+1]=0;
}
}
if(j-1>=0 && j+1<N && i+1<M){
if(grid[i][j]+grid[i][j-1]+grid[i][j+1]+grid[i+1][j]==0){
grid[i][j]=grid[i][j-1]=grid[i][j+1]=grid[i+1][j]=1;
int d=f(x+1);
if(d!=-1) s3 = a[i][j]+a[i][j-1]+a[i][j+1]+a[i+1][j]+d;
grid[i][j]=grid[i][j-1]=grid[i][j+1]=grid[i+1][j]=0;
}
}
if(j-1>=0 && j+1<N && i-1>=0){
if(grid[i][j]+grid[i][j-1]+grid[i][j+1]+grid[i-1][j]==0){
grid[i][j]=grid[i][j-1]=grid[i][j+1]=grid[i-1][j]=1;
int d=f(x+1);
if(d!=-1) s4 = a[i][j]+a[i][j-1]+a[i][j+1]+a[i-1][j]+d;
grid[i][j]=grid[i][j-1]=grid[i][j+1]=grid[i-1][j]=0;
}
}
return max(s1, max(s2, max(s3, s4)));
}
int main()
{
scanf("%d%d", &M, &N);
a.resize(M, vector<int>(N));
grid.resize(M, vector<int>(N));
for(int i=0; i < M; i++){
for(int j=0; j < N; j++)
scanf("%d", &a[i][j]);
}
scanf("%d", &K);
sp.resize(K);
for(int i=0; i < K; i++){
scanf("%d%d", &sp[i].first, &sp[i].second);
}
sort(sp.begin(), sp.end());
if(K <= 10){
int ans=f(0);
if(ans>=0) printf("%d\n", ans);
else printf("No\n");
}
else if(sp[0].first==sp.back().first){
memset(memo, -1, sizeof memo);
int s1=-1, s2=-1, s3=-1, s4=-1;
int i=sp[0].first, j=sp[0].second;
if(i-1>=0 && i+1<M && j-1>=0) s1=a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j-1]+dp(1, 1);
if(i-1>=0 && i+1<M && j+1<N) s2=a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j+1]+dp(1, 2);
if(j-1>=0 && j+1<N && i-1>=0) s3=a[i][j]+a[i][j-1]+a[i][j+1]+a[i-1][j]+dp(1, 3);
if(j-1>=0 && j+1<N && i+1>M) s4=a[i][j]+a[i][j-1]+a[i][j+1]+a[i+1][j]+dp(1, 4);
int ans=max(s1, max(s2, max(s3, s4)));
if(ans==-1) printf("No\n");
else printf("%d\n", ans);
}
else{
for(int i=0; i < K; i++){
grid[sp[i].first][sp[i].second] = 1;
}
int sum=0;
bool valid=true;
for(int x=0; x < K; x++){
int i=sp[x].first, j=sp[x].second;
int s1=-1, s2=-1, s3=-1, s4=-1;
if(i-1>=0 && i+1<M && j-1>=0 && grid[i-1][j]+grid[i+1][j]+grid[i][j-1]==0)
s1=a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j-1];
if(i-1>=0 && i+1<M && j+1<N && grid[i-1][j]+grid[i+1][j]+grid[i][j+1]==0)
s2=a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j+1];
if(j-1>=0 && j+1<N && i-1>=0 && grid[i][j-1]+grid[i][j+1]+grid[i-1][j]==0)
s3=a[i][j]+a[i][j-1]+a[i][j+1]+a[i-1][j];
if(j-1>=0 && j+1<N && i+1<M && grid[i][j-1]+grid[i][j+1]+grid[i+1][j]==0)
s4=a[i][j]+a[i][j-1]+a[i][j+1]+a[i+1][j];
int d=max(s1, max(s2, max(s3, s4)));
if(d==-1){
valid=false;
break;
}
sum += d;
}
if(!valid) printf("No\n");
else printf("%d\n", sum);
}
}
Compilation message
covering.cpp: In function 'int main()':
covering.cpp:161:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | scanf("%d%d", &M, &N);
| ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | scanf("%d", &a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
168 | scanf("%d", &K);
| ~~~~~^~~~~~~~~~
covering.cpp:171:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | scanf("%d%d", &sp[i].first, &sp[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
344 KB |
Output is correct |
| 2 |
Correct |
3 ms |
600 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1624 KB |
Output is correct |
| 4 |
Correct |
20 ms |
3600 KB |
Output is correct |
| 5 |
Correct |
65 ms |
10380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
20 ms |
3620 KB |
Output is correct |
| 5 |
Correct |
65 ms |
10376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
1116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
344 KB |
Output is correct |
| 2 |
Correct |
3 ms |
600 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1624 KB |
Output is correct |
| 4 |
Correct |
20 ms |
3600 KB |
Output is correct |
| 5 |
Correct |
65 ms |
10380 KB |
Output is correct |
| 6 |
Correct |
15 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
604 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1484 KB |
Output is correct |
| 9 |
Correct |
20 ms |
3620 KB |
Output is correct |
| 10 |
Correct |
65 ms |
10376 KB |
Output is correct |
| 11 |
Correct |
4 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
344 KB |
Output is correct |
| 2 |
Correct |
3 ms |
600 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1624 KB |
Output is correct |
| 4 |
Correct |
20 ms |
3600 KB |
Output is correct |
| 5 |
Correct |
65 ms |
10380 KB |
Output is correct |
| 6 |
Correct |
15 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
604 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1484 KB |
Output is correct |
| 9 |
Correct |
20 ms |
3620 KB |
Output is correct |
| 10 |
Correct |
65 ms |
10376 KB |
Output is correct |
| 11 |
Correct |
4 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
