#include <bits/stdc++.h>
using namespace std;
int dx[] = {0,0,1,-1,1,-1,1,-1};
int dy[] = {1,-1,0,0,1,-1,-1,1};
vector<pair<int,int>> grupa;
vector<vector<pair<int,int>>> gr;
int n,m,k,a[1005][1005],sp[1005][1005];
bool sel[1005][1005];
void Fill(int x, int y)
{
grupa.push_back({x,y});
sp[x][y] = false;
for(int p=0;p<8;p++)
{
int xx = x + dx[p];
int yy = y + dy[p];
if(sp[xx][yy])
{
Fill(xx,yy);
}
}
}
void bordare()
{
for(int i=0;i<=n+1;i++)
{
sel[i][0] = sel[i][m+1] = true;
}
for(int i=0;i<=m+1;i++)
{
sel[0][i] = sel[n+1][i] = true;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
bordare();
cin>>k;
for(int i=1;i<=k;i++)
{
int x,y;
cin>>x>>y;
++x;
++y;
sp[x][y] = true;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!sp[i][j])
{
continue;
}
grupa.clear();
Fill(i,j);
if(grupa.size()>2)
{
cout<<"No"<<'\n';
return 0;
}
gr.push_back(grupa);
}
}
long long sum = 0;
for(auto v : gr)
{
if(v.size()==1)
{
continue;
}
pair<int,int> x = v[0];
pair<int,int> y = v[1];
if(x.first==y.first)
{
if(x.second>y.second)
{
swap(x,y);
}
int i = x.first;
int j = x.second;
if(sel[i][j] || sel[i][j-1] || sel[i-1][j] || sel[i+1][j] || sel[i][j+1] || sel[i][j+2] || sel[i-1][j+1] || sel[i+1][j+1])
{
cout<<"No"<<'\n';
return 0;
}
sum += (a[i][j] + a[i][j-1] + a[i-1][j] + a[i+1][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+1] + a[i+1][j+1]);
sel[i][j] = sel[i][j-1] = sel[i-1][j] = sel[i+1][j] = sel[i][j+1] = sel[i][j+2] = sel[i-1][j+1] = sel[i+1][j+1] = true;
}
else if(x.second==y.second)
{
if(x.first>y.first)
{
swap(x,y);
}
int i = x.first;
int j = x.second;
if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j] || sel[i+2][j] || sel[i+1][j-1] || sel[i+1][j+1])
{
cout<<"No"<<'\n';
return 0;
}
sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j] + a[i+2][j] + a[i+1][j-1] + a[i+1][j+1]);
sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j] = sel[i+2][j] = sel[i+1][j-1] = sel[i+1][j+1] = true;
}
else if((x.first<y.first && x.second<y.second) || (x.first>y.first && x.second>y.second))
{
if(x.first>y.first)
{
swap(x,y);
}
int i = x.first;
int j = x.second;
if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j+1] || sel[i+2][j+1] || sel[i+1][j] || sel[i+1][j+2])
{
cout<<"No"<<'\n';
return 0;
}
sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1] + a[i+1][j] + a[i+1][j+2]);
sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j+1] = sel[i+2][j+1] = sel[i+1][j] = sel[i+1][j+2] = true;
}
else
{
if(x.first>y.first)
{
swap(x,y);
}
int i = x.first;
int j = x.second;
if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j-1] || sel[i+2][j-1] || sel[i+1][j-2] || sel[i+1][j])
{
cout<<"No"<<'\n';
return 0;
}
sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j-1] + a[i+2][j-1] + a[i+1][j-2] + a[i+1][j]);
sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j-1] = sel[i+2][j-1] = sel[i+1][j-2] = sel[i+1][j] = true;
}
}
for(auto v : gr)
{
if(v.size()==2)
{
continue;
}
int i = v[0].first;
int j = v[0].second;
int Max = 0;
if(!sel[i][j] && !sel[i+1][j] && !sel[i][j-1] && !sel[i][j+1])
{
Max = max(Max,a[i][j] + a[i+1][j] + a[i][j-1] + a[i][j+1]);
}
if(!sel[i][j] && !sel[i-1][j] && !sel[i][j-1] && !sel[i][j+1])
{
Max = max(Max,a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1]);
}
if(!sel[i][j] && !sel[i][j+1] && !sel[i-1][j] && !sel[i+1][j])
{
Max = max(Max,a[i][j] + a[i][j+1] + a[i-1][j] + a[i+1][j]);
}
if(!sel[i][j] && !sel[i][j-1] && !sel[i-1][j] && !sel[i+1][j])
{
Max = max(Max,a[i][j] + a[i][j-1] + a[i-1][j] + a[i+1][j]);
}
if(!Max)
{
cout<<"No"<<'\n';
return 0;
}
if(Max==a[i][j]+a[i+1][j]+a[i][j-1]+a[i][j+1])
{
sel[i][j] = sel[i+1][j] = sel[i][j-1] = sel[i][j+1] = true;
}
else if(Max==a[i][j]+a[i-1][j]+a[i][j-1]+a[i][j+1])
{
sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = true;
}
else if(Max==a[i][j]+a[i][j+1]+a[i-1][j]+a[i+1][j])
{
sel[i][j] = sel[i][j+1] = sel[i-1][j] = sel[i+1][j] = true;
}
else if(Max==a[i][j]+a[i][j-1]+a[i-1][j]+a[i+1][j])
{
sel[i][j] = sel[i][j-1] = sel[i-1][j] = sel[i+1][j] = true;
}
sum+=Max;
}
cout<<sum<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
844 KB |
Output is correct |
2 |
Correct |
9 ms |
1996 KB |
Output is correct |
3 |
Correct |
26 ms |
1904 KB |
Output is correct |
4 |
Correct |
77 ms |
6524 KB |
Output is correct |
5 |
Correct |
254 ms |
11720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
844 KB |
Output is correct |
2 |
Correct |
9 ms |
2076 KB |
Output is correct |
3 |
Correct |
27 ms |
1952 KB |
Output is correct |
4 |
Correct |
79 ms |
6600 KB |
Output is correct |
5 |
Correct |
255 ms |
11616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
844 KB |
Output is correct |
2 |
Correct |
9 ms |
1996 KB |
Output is correct |
3 |
Correct |
26 ms |
1972 KB |
Output is correct |
4 |
Correct |
77 ms |
6556 KB |
Output is correct |
5 |
Correct |
280 ms |
11432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
844 KB |
Output is correct |
2 |
Correct |
9 ms |
1996 KB |
Output is correct |
3 |
Correct |
26 ms |
1904 KB |
Output is correct |
4 |
Correct |
77 ms |
6524 KB |
Output is correct |
5 |
Correct |
254 ms |
11720 KB |
Output is correct |
6 |
Correct |
3 ms |
844 KB |
Output is correct |
7 |
Correct |
9 ms |
2076 KB |
Output is correct |
8 |
Correct |
27 ms |
1952 KB |
Output is correct |
9 |
Correct |
79 ms |
6600 KB |
Output is correct |
10 |
Correct |
255 ms |
11616 KB |
Output is correct |
11 |
Correct |
3 ms |
844 KB |
Output is correct |
12 |
Correct |
9 ms |
1996 KB |
Output is correct |
13 |
Correct |
26 ms |
1972 KB |
Output is correct |
14 |
Correct |
77 ms |
6556 KB |
Output is correct |
15 |
Correct |
280 ms |
11432 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
844 KB |
Output is correct |
2 |
Correct |
9 ms |
1996 KB |
Output is correct |
3 |
Correct |
26 ms |
1904 KB |
Output is correct |
4 |
Correct |
77 ms |
6524 KB |
Output is correct |
5 |
Correct |
254 ms |
11720 KB |
Output is correct |
6 |
Correct |
3 ms |
844 KB |
Output is correct |
7 |
Correct |
9 ms |
2076 KB |
Output is correct |
8 |
Correct |
27 ms |
1952 KB |
Output is correct |
9 |
Correct |
79 ms |
6600 KB |
Output is correct |
10 |
Correct |
255 ms |
11616 KB |
Output is correct |
11 |
Correct |
3 ms |
844 KB |
Output is correct |
12 |
Correct |
9 ms |
1996 KB |
Output is correct |
13 |
Correct |
26 ms |
1972 KB |
Output is correct |
14 |
Correct |
77 ms |
6556 KB |
Output is correct |
15 |
Correct |
280 ms |
11432 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |