#include <bits/stdc++.h>
using namespace std;
int m,n;
int fct(int x, int y)
{
x--;
y--;
return m*x+y;
}
int v[1000005];
int f[1000005];
bool viz[1000005];
pair<int,int>red[1000005];
bool oc[1000005];
vector<int>graf[1000005];
struct sus
{
int nrmuch=0, nrnod=0, minn=2100000000;
};
sus dfs(int nod)
{
sus ans;
if(viz[nod])
return ans;
viz[nod]=true;
ans.nrnod=1;
ans.nrmuch=graf[nod].size();
int a=red[nod].first;
int b=red[nod].second;
if(a>1)
ans.minn=min(ans.minn,v[fct(a-1,b)]),oc[fct(a-1,b)]=true;
if(b>1)
ans.minn=min(ans.minn,v[fct(a,b-1)]),oc[fct(a,b-1)]=true;
if(b<m)
ans.minn=min(ans.minn,v[fct(a,b+1)]),oc[fct(a,b+1)]=true;
if(a<n)
ans.minn=min(ans.minn,v[fct(a+1,b)]),oc[fct(a+1,b)]=true;
for(int i=0;i<graf[nod].size();i++)
{
sus p=dfs(graf[nod][i]);
ans.nrnod+=p.nrnod;
ans.nrmuch+=p.nrmuch;
ans.minn=min(ans.minn,p.minn);
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>v[fct(i,j)];
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>red[i].first>>red[i].second;
red[i].first++;
red[i].second++;
oc[fct(red[i].first,red[i].second)]=true;
f[fct(red[i].first,red[i].second)]=i;
}
for(int i=1;i<=k;i++)
{
int a=red[i].first;
int b=red[i].second;
if(a==1)
graf[i].push_back(i),graf[i].push_back(i);
if(a==n)
graf[i].push_back(i),graf[i].push_back(i);
if(b==1)
graf[i].push_back(i),graf[i].push_back(i);
if(b==m)
graf[i].push_back(i),graf[i].push_back(i);
if(a>1 && b<m && f[fct(a-1,b+1)])
graf[i].push_back(f[fct(a-1,b+1)]),graf[f[fct(a-1,b+1)]].push_back(i),graf[i].push_back(f[fct(a-1,b+1)]),graf[f[fct(a-1,b+1)]].push_back(i);
if(b<m && f[fct(a,b+1)])
graf[i].push_back(f[fct(a,b+1)]),graf[f[fct(a,b+1)]].push_back(i),graf[i].push_back(f[fct(a,b+1)]),graf[f[fct(a,b+1)]].push_back(i);
if(b<m-1 && f[fct(a,b+2)])
graf[i].push_back(f[fct(a,b+2)]),graf[f[fct(a,b+2)]].push_back(i);
if(b<m && a<n && f[fct(a+1,b+1)])
graf[i].push_back(f[fct(a+1,b+1)]),graf[f[fct(a+1,b+1)]].push_back(i),graf[i].push_back(f[fct(a+1,b+1)]),graf[f[fct(a+1,b+1)]].push_back(i);
if(a<n && f[fct(a+1,b)])
graf[i].push_back(f[fct(a+1,b)]),graf[f[fct(a+1,b)]].push_back(i),graf[i].push_back(f[fct(a+1,b)]),graf[f[fct(a+1,b)]].push_back(i);
if(a<n-1 && f[fct(a+2,b)])
graf[i].push_back(f[fct(a+2,b)]),graf[f[fct(a+2,b)]].push_back(i);
}
int ans=0;
for(int i=1;i<=k;i++)
{
if(!viz[i])
{
sus x=dfs(i);
x.nrmuch/=2;
if(x.nrmuch<x.nrnod)
ans+=x.minn;
if(x.nrmuch>x.nrnod)
{
cout<<"No";
return 0;
}
}
}
int ras=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(oc[fct(i,j)])
ras+=v[fct(i,j)];
cout<<ras-ans;
}
Compilation message
covering.cpp: In function 'sus dfs(int)':
covering.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<graf[nod].size();i++)
| ~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23892 KB |
Output is correct |
2 |
Correct |
21 ms |
24056 KB |
Output is correct |
3 |
Correct |
39 ms |
24944 KB |
Output is correct |
4 |
Correct |
70 ms |
27348 KB |
Output is correct |
5 |
Correct |
213 ms |
34892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23932 KB |
Output is correct |
2 |
Correct |
18 ms |
24148 KB |
Output is correct |
3 |
Correct |
35 ms |
24932 KB |
Output is correct |
4 |
Correct |
74 ms |
27324 KB |
Output is correct |
5 |
Correct |
228 ms |
35004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23892 KB |
Output is correct |
2 |
Correct |
18 ms |
24192 KB |
Output is correct |
3 |
Correct |
30 ms |
24980 KB |
Output is correct |
4 |
Correct |
71 ms |
27276 KB |
Output is correct |
5 |
Correct |
214 ms |
34924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23756 KB |
Output is correct |
3 |
Correct |
21 ms |
24196 KB |
Output is correct |
4 |
Correct |
18 ms |
24060 KB |
Output is correct |
5 |
Correct |
37 ms |
24608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
12 ms |
23804 KB |
Output is correct |
4 |
Correct |
13 ms |
23728 KB |
Output is correct |
5 |
Correct |
12 ms |
23800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23892 KB |
Output is correct |
2 |
Correct |
21 ms |
24056 KB |
Output is correct |
3 |
Correct |
39 ms |
24944 KB |
Output is correct |
4 |
Correct |
70 ms |
27348 KB |
Output is correct |
5 |
Correct |
213 ms |
34892 KB |
Output is correct |
6 |
Correct |
17 ms |
23932 KB |
Output is correct |
7 |
Correct |
18 ms |
24148 KB |
Output is correct |
8 |
Correct |
35 ms |
24932 KB |
Output is correct |
9 |
Correct |
74 ms |
27324 KB |
Output is correct |
10 |
Correct |
228 ms |
35004 KB |
Output is correct |
11 |
Correct |
14 ms |
23892 KB |
Output is correct |
12 |
Correct |
18 ms |
24192 KB |
Output is correct |
13 |
Correct |
30 ms |
24980 KB |
Output is correct |
14 |
Correct |
71 ms |
27276 KB |
Output is correct |
15 |
Correct |
214 ms |
34924 KB |
Output is correct |
16 |
Correct |
12 ms |
23764 KB |
Output is correct |
17 |
Correct |
13 ms |
23756 KB |
Output is correct |
18 |
Correct |
21 ms |
24196 KB |
Output is correct |
19 |
Correct |
18 ms |
24060 KB |
Output is correct |
20 |
Correct |
37 ms |
24608 KB |
Output is correct |
21 |
Correct |
16 ms |
23892 KB |
Output is correct |
22 |
Correct |
23 ms |
24268 KB |
Output is correct |
23 |
Correct |
32 ms |
24984 KB |
Output is correct |
24 |
Correct |
77 ms |
27352 KB |
Output is correct |
25 |
Correct |
216 ms |
34980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23892 KB |
Output is correct |
2 |
Correct |
21 ms |
24056 KB |
Output is correct |
3 |
Correct |
39 ms |
24944 KB |
Output is correct |
4 |
Correct |
70 ms |
27348 KB |
Output is correct |
5 |
Correct |
213 ms |
34892 KB |
Output is correct |
6 |
Correct |
17 ms |
23932 KB |
Output is correct |
7 |
Correct |
18 ms |
24148 KB |
Output is correct |
8 |
Correct |
35 ms |
24932 KB |
Output is correct |
9 |
Correct |
74 ms |
27324 KB |
Output is correct |
10 |
Correct |
228 ms |
35004 KB |
Output is correct |
11 |
Correct |
14 ms |
23892 KB |
Output is correct |
12 |
Correct |
18 ms |
24192 KB |
Output is correct |
13 |
Correct |
30 ms |
24980 KB |
Output is correct |
14 |
Correct |
71 ms |
27276 KB |
Output is correct |
15 |
Correct |
214 ms |
34924 KB |
Output is correct |
16 |
Correct |
12 ms |
23764 KB |
Output is correct |
17 |
Correct |
13 ms |
23756 KB |
Output is correct |
18 |
Correct |
21 ms |
24196 KB |
Output is correct |
19 |
Correct |
18 ms |
24060 KB |
Output is correct |
20 |
Correct |
37 ms |
24608 KB |
Output is correct |
21 |
Correct |
13 ms |
23764 KB |
Output is correct |
22 |
Correct |
12 ms |
23764 KB |
Output is correct |
23 |
Correct |
12 ms |
23804 KB |
Output is correct |
24 |
Correct |
13 ms |
23728 KB |
Output is correct |
25 |
Correct |
12 ms |
23800 KB |
Output is correct |
26 |
Correct |
16 ms |
23892 KB |
Output is correct |
27 |
Correct |
23 ms |
24268 KB |
Output is correct |
28 |
Correct |
32 ms |
24984 KB |
Output is correct |
29 |
Correct |
77 ms |
27352 KB |
Output is correct |
30 |
Correct |
216 ms |
34980 KB |
Output is correct |
31 |
Correct |
358 ms |
45172 KB |
Output is correct |
32 |
Correct |
201 ms |
34188 KB |
Output is correct |
33 |
Correct |
205 ms |
37452 KB |
Output is correct |
34 |
Correct |
219 ms |
33900 KB |
Output is correct |
35 |
Correct |
272 ms |
42332 KB |
Output is correct |