#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
ll dx[4] = {0,0,1,-1};
ll dy[4] = {1,-1,0,0};
vector<vector<bool> >v;
bool in(ll n,ll m,ll x,ll y){
return min(x,y) >= 0 && x < n && y < m;
}
vector<vector<vector<ii> > >adj;
vector<ll>exo;
set<ii>ar;
vector<vector<ll> >arr;
ll posa = 0;
void dfs(ll x,ll y){
v[x][y] = true;
if(!ar.count(ii(x,y))){
exo.pb(arr[x][y]);
}
else{
posa++;
}
for(auto z:adj[x][y]){
if(!v[z.F][z.S]){
dfs(z.F,z.S);
}
}
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,m;
cin>>n>>m;
f(i,0,n){
arr.pb(vector<ll>());
v.pb(vector<bool>());
f(j,0,m){
ll a;
cin>>a;
arr.back().pb(a);
v.back().pb(0);
}
}
vector<vector<ii> > w(m);
adj.assign(n,w);
ll ans = 0;
bool ok = true;
ll k;
cin>>k;
f(i,0,k){
ll x,y;
cin>>x>>y;
ar.insert(ii(x,y));
ans += arr[x][y];
f(e,0,4){
if(in(n,m,x + dx[e],y + dy[e])){
adj[x][y].pb(ii(x + dx[e],y + dy[e]));
adj[x + dx[e]][y + dy[e]].pb(ii(x,y));
}
}
}
f(i,0,n){
f(j,0,m){
if(!v[i][j]){
posa = 0;
exo.clear();
dfs(i,j);
sort(all(exo));
posa *= 3;
if(posa > exo.size()){
ok = false;
}
else{
while(posa--){
ans += exo.back();
exo.pop_back();
}
}
}
}
}
if(!ok){
cout<<"No\n";
return 0;
}
cout<<ans<<"\n";
}
/*
5 6
7 3 8 1 0 9
4 6 2 5 8 3
1 9 7 3 9 5
2 6 8 4 5 7
3 8 2 7 3 6
3
1 1
2 2
3 4
*/
Compilation message
covering.cpp: In function 'int main()':
covering.cpp:91:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if(posa > exo.size()){
| ~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
5 ms |
1364 KB |
Output is correct |
3 |
Correct |
14 ms |
3492 KB |
Output is correct |
4 |
Correct |
45 ms |
10612 KB |
Output is correct |
5 |
Correct |
153 ms |
32276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
5 ms |
1392 KB |
Output is correct |
3 |
Correct |
14 ms |
3512 KB |
Output is correct |
4 |
Correct |
44 ms |
10620 KB |
Output is correct |
5 |
Correct |
148 ms |
32332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
5 ms |
1268 KB |
Output is correct |
3 |
Correct |
15 ms |
3540 KB |
Output is correct |
4 |
Correct |
43 ms |
10652 KB |
Output is correct |
5 |
Correct |
149 ms |
32316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
7 ms |
2124 KB |
Output is correct |
4 |
Correct |
5 ms |
1608 KB |
Output is correct |
5 |
Correct |
16 ms |
4364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
5 ms |
1364 KB |
Output is correct |
3 |
Correct |
14 ms |
3492 KB |
Output is correct |
4 |
Correct |
45 ms |
10612 KB |
Output is correct |
5 |
Correct |
153 ms |
32276 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
5 ms |
1392 KB |
Output is correct |
8 |
Correct |
14 ms |
3512 KB |
Output is correct |
9 |
Correct |
44 ms |
10620 KB |
Output is correct |
10 |
Correct |
148 ms |
32332 KB |
Output is correct |
11 |
Correct |
2 ms |
588 KB |
Output is correct |
12 |
Correct |
5 ms |
1268 KB |
Output is correct |
13 |
Correct |
15 ms |
3540 KB |
Output is correct |
14 |
Correct |
43 ms |
10652 KB |
Output is correct |
15 |
Correct |
149 ms |
32316 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
7 ms |
2124 KB |
Output is correct |
19 |
Correct |
5 ms |
1608 KB |
Output is correct |
20 |
Correct |
16 ms |
4364 KB |
Output is correct |
21 |
Correct |
2 ms |
716 KB |
Output is correct |
22 |
Correct |
5 ms |
1484 KB |
Output is correct |
23 |
Correct |
15 ms |
3912 KB |
Output is correct |
24 |
Correct |
46 ms |
11676 KB |
Output is correct |
25 |
Correct |
148 ms |
34780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
5 ms |
1364 KB |
Output is correct |
3 |
Correct |
14 ms |
3492 KB |
Output is correct |
4 |
Correct |
45 ms |
10612 KB |
Output is correct |
5 |
Correct |
153 ms |
32276 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
5 ms |
1392 KB |
Output is correct |
8 |
Correct |
14 ms |
3512 KB |
Output is correct |
9 |
Correct |
44 ms |
10620 KB |
Output is correct |
10 |
Correct |
148 ms |
32332 KB |
Output is correct |
11 |
Correct |
2 ms |
588 KB |
Output is correct |
12 |
Correct |
5 ms |
1268 KB |
Output is correct |
13 |
Correct |
15 ms |
3540 KB |
Output is correct |
14 |
Correct |
43 ms |
10652 KB |
Output is correct |
15 |
Correct |
149 ms |
32316 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
7 ms |
2124 KB |
Output is correct |
19 |
Correct |
5 ms |
1608 KB |
Output is correct |
20 |
Correct |
16 ms |
4364 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
2 ms |
716 KB |
Output is correct |
27 |
Correct |
5 ms |
1484 KB |
Output is correct |
28 |
Correct |
15 ms |
3912 KB |
Output is correct |
29 |
Correct |
46 ms |
11676 KB |
Output is correct |
30 |
Correct |
148 ms |
34780 KB |
Output is correct |
31 |
Correct |
710 ms |
79740 KB |
Output is correct |
32 |
Correct |
179 ms |
37068 KB |
Output is correct |
33 |
Correct |
193 ms |
42692 KB |
Output is correct |
34 |
Correct |
166 ms |
36696 KB |
Output is correct |
35 |
Correct |
388 ms |
54728 KB |
Output is correct |