#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<long long , long long>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 1e5 + 100;
const long long mod = 1e9 + 7 ;
typedef long long ll;
ll l,r,mid;
ll n,m;
bool isval(int mid){
//cout << mid <<" " << mid*mid-mid <<endl;
if (((mid-1)*mid)/2 < m) return 0;
return 1;
}
int darage[maxm] , ss , mm;
queue<pi> q;
vector<int> g[maxm] , z[maxm];
bool vis[maxm] , gos[maxm];
set<pi> st;
pi w[maxm];
//ll rw[maxm][maxm];
int k, t;
vector <int> a[maxm];
vector <bool> siv[maxm];
int X[4] = {-1, 0, 1, 0}, Y[4] = {0, 1, 0, -1};
int X2[4] = {-1, 1, 1, -1}, Y2[4] = {1, 1, -1, -1};
int bd[maxm];
inline bool f(int x, int y){ return ((x>=1)&&(y>=1)&&(x<=n)&&(y<=m));}
int h(int x, int y){ return (x-1)*m+y;}
void wef(int x, int y, int d){
siv[x][y] = 0;
mid += a[x][y];
a[x][y] = -mod;
for (int i=0; i<4; i++) {
if (i==d) continue;
mid += a[x + X[i]][y + Y[i]];
a[x + X[i]][y + Y[i]] = -mod;
}
}
void dfs(int v, int p){
vis[v] = 1;
int x=(v-1)/m+1, y=(v-1)%m+1;
for (int i = 0; i < 4; i++)
darage[t] = min(a[x+X[i]][y+Y[i]],darage[t]);
for (int u:g[v]) {
if (u==p) continue;
if (!vis[u]) dfs(u,v);
else if (vis[u]==1) bd[t]++;
}
vis[v]=2;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0; i<n+3; i++) for(int j=0; j<m+3; j++) siv[i].push_back(0) , a[i].push_back(-mod);
for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>a[i][j];
cin>>k;
for (int i=1; i<=k; i++){
cin >>l>>r , l++ , r++;
siv[l][r] = 1;
}
for (int x=1; x<=n; x++){
for (int y=1; y<=m; y++){
for (int i = 0; i < 4; i++){
if (siv[x][y] && siv[x + X[i]][y + Y[i]]){
wef(x, y, i) , wef(x+X[i], y+Y[i], (i+2)&3);
}
if (siv[x][y] && siv[x + X2[i]][y + Y2[i]]){
wef(x, y, i) , wef(x+X2[i], y+Y2[i], (i+2)&3);
}
}
}
}
for (int x=1; x<=n; x++) for (int y=1; y<=m; y++){
if (!siv[x][y]) continue;
mid+=a[x][y];
for (int i=0; i<4; i++) mid+=a[x+X[i]][y+Y[i]];
}
for (int x=1; x<=n; x++){
for (int y=1; y<=m; y++){
for (int i=0; i<2; i++){
if (f(x+2*X[i], y+2*Y[i]) && siv[x+2*X[i]][y+2*Y[i]] && siv[x][y]) {
l=h(x,y) , r=h(x+2*X[i], y+2*Y[i]);
mid-=a[x+X[i]][y+Y[i]];
g[l].push_back(r);
g[r].push_back(l);
}
}
}
}
for (int x = 1; x <= n; x++){
for (int y = 1; y <= m; y++){
if (!siv[x][y]) continue;
int v = h(x, y);
if (vis[v]) continue;
t++;
darage[t]=mod;
dfs(v,v);
if (bd[t]>1) return cout<<"No",0;
if (bd[t]==0) mid-=darage[t];
}
}
if (mid<0) return cout<<"No",0;
cout<<mid;
}
Compilation message
covering.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
5 | #pragma comment(linker, "/stack:200000000")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11348 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12136 KB |
Output is correct |
| 4 |
Runtime error |
38 ms |
27196 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11380 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11604 KB |
Output is correct |
| 3 |
Correct |
15 ms |
12116 KB |
Output is correct |
| 4 |
Runtime error |
43 ms |
27328 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11348 KB |
Output is correct |
| 2 |
Correct |
9 ms |
11604 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12224 KB |
Output is correct |
| 4 |
Runtime error |
39 ms |
27208 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11220 KB |
Output is correct |
| 2 |
Correct |
6 ms |
11220 KB |
Output is correct |
| 3 |
Correct |
10 ms |
11840 KB |
Output is correct |
| 4 |
Correct |
9 ms |
11668 KB |
Output is correct |
| 5 |
Correct |
17 ms |
12392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11348 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12136 KB |
Output is correct |
| 4 |
Runtime error |
38 ms |
27196 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11348 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12136 KB |
Output is correct |
| 4 |
Runtime error |
38 ms |
27196 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
