#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=1004004;
bool ok[MAX_N];
int a[MAX_N];
bool used[MAX_N];
int q;
int ans;
int cnt;
int n,m;
vector<int>g[MAX_N];
vector<int>v;
int i,j;
int x,y;
int t,t1,t2,t3,t4;
int tmp;
void Read()
{
cin>>n>>m;
tmp=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[tmp];
tmp++;
}
}
cin>>q;
for(i=1;i<=q;i++)
{
cin>>x>>y;
x++;
y++;
t=(x-1)*m+y;
t1=(x-2)*m+y;
t2=(x)*m+y;
t3=(x-1)*m+y-1;
t4=(x-1)*m+y+1;
ok[t]=1;
ans+=a[t];
if(x>1)
{
g[t].push_back(t1);
g[t1].push_back(t);
}
if(x<n)
{
g[t].push_back(t2);
g[t2].push_back(t);
}
if(y>1)
{
g[t].push_back(t3);
g[t3].push_back(t);
}
if(y<m)
{
g[t].push_back(t4);
g[t4].push_back(t);
}
}
}
void DFS(int u)
{
if(ok[u])cnt++;
else v.push_back(a[u]);
used[u]=1;
for(auto v:g[u])
{
if(!used[v])DFS(v);
}
}
int r;
void Solve()
{
tmp=1;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(!used[tmp])
{
v.clear();
cnt=0;
DFS((i-1)*m+j);
if(3*cnt>v.size())
{
cout<<"No\n";
return;
}
sort(v.rbegin(),v.rend());
for(r=0;r<3*cnt;r++)
{
ans+=v[r];
}
}
tmp++;
}
}
cout<<ans<<"\n";
}
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Read();
Solve();
return 0;
}
Compilation message
covering.cpp: In function 'void Solve()':
covering.cpp:90:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if(3*cnt>v.size())
| ~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24020 KB |
Output is correct |
2 |
Correct |
19 ms |
24168 KB |
Output is correct |
3 |
Correct |
26 ms |
24804 KB |
Output is correct |
4 |
Correct |
37 ms |
26812 KB |
Output is correct |
5 |
Correct |
107 ms |
31068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24020 KB |
Output is correct |
2 |
Correct |
16 ms |
24180 KB |
Output is correct |
3 |
Correct |
22 ms |
24796 KB |
Output is correct |
4 |
Correct |
35 ms |
26564 KB |
Output is correct |
5 |
Correct |
92 ms |
30744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24020 KB |
Output is correct |
2 |
Correct |
15 ms |
24148 KB |
Output is correct |
3 |
Correct |
19 ms |
24812 KB |
Output is correct |
4 |
Correct |
40 ms |
26828 KB |
Output is correct |
5 |
Correct |
104 ms |
32548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23892 KB |
Output is correct |
2 |
Correct |
15 ms |
23872 KB |
Output is correct |
3 |
Correct |
16 ms |
24360 KB |
Output is correct |
4 |
Correct |
15 ms |
24176 KB |
Output is correct |
5 |
Correct |
21 ms |
24836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
23912 KB |
Output is correct |
2 |
Correct |
13 ms |
23816 KB |
Output is correct |
3 |
Correct |
11 ms |
23892 KB |
Output is correct |
4 |
Correct |
14 ms |
23912 KB |
Output is correct |
5 |
Correct |
12 ms |
23860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24020 KB |
Output is correct |
2 |
Correct |
19 ms |
24168 KB |
Output is correct |
3 |
Correct |
26 ms |
24804 KB |
Output is correct |
4 |
Correct |
37 ms |
26812 KB |
Output is correct |
5 |
Correct |
107 ms |
31068 KB |
Output is correct |
6 |
Correct |
12 ms |
24020 KB |
Output is correct |
7 |
Correct |
16 ms |
24180 KB |
Output is correct |
8 |
Correct |
22 ms |
24796 KB |
Output is correct |
9 |
Correct |
35 ms |
26564 KB |
Output is correct |
10 |
Correct |
92 ms |
30744 KB |
Output is correct |
11 |
Correct |
12 ms |
24020 KB |
Output is correct |
12 |
Correct |
15 ms |
24148 KB |
Output is correct |
13 |
Correct |
19 ms |
24812 KB |
Output is correct |
14 |
Correct |
40 ms |
26828 KB |
Output is correct |
15 |
Correct |
104 ms |
32548 KB |
Output is correct |
16 |
Correct |
12 ms |
23892 KB |
Output is correct |
17 |
Correct |
15 ms |
23872 KB |
Output is correct |
18 |
Correct |
16 ms |
24360 KB |
Output is correct |
19 |
Correct |
15 ms |
24176 KB |
Output is correct |
20 |
Correct |
21 ms |
24836 KB |
Output is correct |
21 |
Correct |
15 ms |
23924 KB |
Output is correct |
22 |
Correct |
15 ms |
24148 KB |
Output is correct |
23 |
Correct |
23 ms |
24808 KB |
Output is correct |
24 |
Correct |
37 ms |
26836 KB |
Output is correct |
25 |
Correct |
92 ms |
33744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
24020 KB |
Output is correct |
2 |
Correct |
19 ms |
24168 KB |
Output is correct |
3 |
Correct |
26 ms |
24804 KB |
Output is correct |
4 |
Correct |
37 ms |
26812 KB |
Output is correct |
5 |
Correct |
107 ms |
31068 KB |
Output is correct |
6 |
Correct |
12 ms |
24020 KB |
Output is correct |
7 |
Correct |
16 ms |
24180 KB |
Output is correct |
8 |
Correct |
22 ms |
24796 KB |
Output is correct |
9 |
Correct |
35 ms |
26564 KB |
Output is correct |
10 |
Correct |
92 ms |
30744 KB |
Output is correct |
11 |
Correct |
12 ms |
24020 KB |
Output is correct |
12 |
Correct |
15 ms |
24148 KB |
Output is correct |
13 |
Correct |
19 ms |
24812 KB |
Output is correct |
14 |
Correct |
40 ms |
26828 KB |
Output is correct |
15 |
Correct |
104 ms |
32548 KB |
Output is correct |
16 |
Correct |
12 ms |
23892 KB |
Output is correct |
17 |
Correct |
15 ms |
23872 KB |
Output is correct |
18 |
Correct |
16 ms |
24360 KB |
Output is correct |
19 |
Correct |
15 ms |
24176 KB |
Output is correct |
20 |
Correct |
21 ms |
24836 KB |
Output is correct |
21 |
Correct |
12 ms |
23912 KB |
Output is correct |
22 |
Correct |
13 ms |
23816 KB |
Output is correct |
23 |
Correct |
11 ms |
23892 KB |
Output is correct |
24 |
Correct |
14 ms |
23912 KB |
Output is correct |
25 |
Correct |
12 ms |
23860 KB |
Output is correct |
26 |
Correct |
15 ms |
23924 KB |
Output is correct |
27 |
Correct |
15 ms |
24148 KB |
Output is correct |
28 |
Correct |
23 ms |
24808 KB |
Output is correct |
29 |
Correct |
37 ms |
26836 KB |
Output is correct |
30 |
Correct |
92 ms |
33744 KB |
Output is correct |
31 |
Correct |
307 ms |
56320 KB |
Output is correct |
32 |
Correct |
74 ms |
34464 KB |
Output is correct |
33 |
Correct |
96 ms |
35568 KB |
Output is correct |
34 |
Correct |
89 ms |
34140 KB |
Output is correct |
35 |
Correct |
178 ms |
44484 KB |
Output is correct |