#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
void ckmn(int&a,int b){a=min(a,b);}
void ckmx(int&a,int b){a=max(a,b);}
const int N=305;
const int inf=1e9+7;
int sz[N],SWX[N][N],SWU[N][N],SWD[N][N],SWR[N][N],x[N],y[N],n,H,W;
int L[N],lsz,T[N],tsz,SM[N*N],U[N*N],D[N*N],R[N*N],ssz,esz;
pii evs[N];
void unq(int*a,int&n){sort(a+1,a+1+n);n=unique(a+1,a+1+n)-a-1;}
int main(){
scanf("%i %i %i",&H,&W,&n);
for(int i=1;i<=n;i++){
scanf("%i %i",&x[i],&y[i]);
L[++lsz]=y[i]-1;
if(y[i]>0)T[++tsz]=y[i]-1;
}
T[++tsz]=W;unq(T,tsz);
for(int i=1;i<=tsz;i++){
esz=0;
for(int j=1;j<=n;j++){
if(y[j]<=T[i]){
SM[++ssz]=T[i]-y[j];
evs[++esz]={T[i]-y[j],x[j]};
}
}
multiset<int> dif,pts;
pts.insert(0);pts.insert(H+1);
dif.insert(H+1);
sort(evs+1,evs+1+esz);
for(int j=1,k;j<=esz;j=k){
for(k=j;k<=esz&&evs[j].first==evs[k].first;k++){
if(pts.find(evs[k].second)==pts.end()){
pts.insert(evs[k].second);
auto it=pts.find(evs[k].second);
dif.erase(*next(it)-*prev(it));
dif.insert(*next(it)-*it);
dif.insert(*it-*prev(it));
}
}
sz[i]++;
SWX[i][sz[i]]=evs[j].first;
SWU[i][sz[i]]=H-*prev(prev(pts.end()));
SWD[i][sz[i]]=*next(pts.begin())-1;
SWR[i][sz[i]]=*dif.rbegin()-1;
}
}
unq(L,lsz);
unq(SM,ssz);
int ans=inf*2;
for(int i=lsz,j=tsz-1;i>=1;i--){
for(;j>=1&&L[i]<T[j];j--){
for(int k=1,o=1;k<=ssz;k++){
while(o<=sz[j]&&SWX[j][o]<=SM[k])o++;
if(o>1)ckmx(U[k],SWU[j][o-1]),ckmx(D[k],SWD[j][o-1]),ckmx(R[k],SWR[j][o-1]);
else U[k]=inf,D[k]=inf,R[k]=inf;
}
}
auto Try=[&](int k,int o){
if(SM[k]<L[i])return;
int r=max(SM[k]-L[i],SWX[tsz][o]);
int _d=max(D[k],SWD[tsz][o]);
int _u=max(U[k],SWU[tsz][o]);
int _r=max(R[k],SWR[tsz][o]);
ckmn(ans,max(_r,_u+_d)+r+L[i]);
};
for(int k=1;k<=ssz;k++){
for(int o=1;o<=sz[tsz];o++){
Try(k,o);
}
}
}
printf("%i\n",ans);
return 0;
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
13 | scanf("%i %i %i",&H,&W,&n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
15 | scanf("%i %i",&x[i],&y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
