#include<bits/stdc++.h>
#define ll long long
#define inf (0x3f3f3f3f)
using namespace std;
vector<int>gx[305],gu[305],gd[305],gs[305];
int vu[90005],vd[90005],vs[90005];
vector<int>aux,aux2,v2;
int a[305],b[305];
int h,w,n,k,l,ans=inf*2;
void calc(vector<pair<int,int>>&auxi,vector<int>&x,vector<int>&u,vector<int>&d,vector<int>&s)
{
sort(auxi.begin(),auxi.end());
multiset<int> st1,st2;
st1.insert(0);
st1.insert(h+1);
st2.insert(h+1);
int i,j,n=auxi.size(),px,py,k;
for(i=0;i<n;i=j){
px=auxi[i].first;
for(j=i+1;j<n && auxi[j].first==px;j++);
for(k=i;k<j;k++){
py=auxi[k].second;
auto it=st1.insert(py);
if (st1.begin()!=it && st1.end()!=next(it))
st2.erase(st2.find(*next(it)-*prev(it)));
if (st1.begin()!=it)
st2.insert(py-*prev(it));
if (st1.end()!=next(it))
st2.insert(*next(it)-py);
}
x.push_back(px);
s.push_back(*prev(st2.end())-1);
u.push_back(*next(st1.begin())-1);
d.push_back(h-*prev(prev(st1.end())));
}
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d%d",&h,&w,&n);
int i;
for(i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
aux.push_back(b[i]-1);
if (b[i]>1)
aux2.push_back(b[i]-1);
}
sort(aux.begin(),aux.end());
sort(aux2.begin(),aux2.end());
aux.erase(unique(aux.begin(),aux.end()),aux.end());
aux2.erase(unique(aux2.begin(),aux2.end()),aux2.end());
k=aux2.size();
aux2.push_back(w);
int x,j,num;
for(i=0;i<=k;i++){
x=aux2[i];
vector<pair<int,int>>auxi;
for(j=1;j<=n;j++){
num=x-b[j];
if (num>=0){
auxi.push_back(make_pair(num,a[j]));
v2.push_back(num);
}
}
calc(auxi,gx[i],gu[i],gd[i],gs[i]);
}
sort(v2.begin(),v2.end());
v2.erase(unique(v2.begin(),v2.end()),v2.end());
l=v2.size();
j=k-1;
int lx,i2,j2;
for(i=aux.size();i--;){
lx=aux[i];
for(;j>=0 && lx<aux[j];j--){
j2=0;
int n=gx[j].size(),x;
for(i2=0;i2<l;i2++){
x=v2[i2];
if (j2<n && gx[j][j2]<=x)
j2++;
if (j2){
vu[i2]=max(vu[i2],gu[j][j2-1]);
vd[i2]=max(vd[i2],gd[j][j2-1]);
vs[i2]=max(vs[i2],gs[j][j2-1]);
}
else
vu[i2]=vd[i2]=vs[i2]=inf;
}
}
int n=gx[k].size(),rx,du,dd,ds;
for(i2=0,j2=0;i2<l || j2<n;){
rx=inf;
if (i2<l)
rx=v2[i2]-lx;
if (j2<n)
rx=min(rx,gx[k][j2]);
if (rx<0){
i2++;
continue;
}
if (i2<l && v2[i2]-lx==rx)
i2++;
if (j2<n && gx[k][j2]==rx)
j2++;
if (i2==0 || j2==0)
continue;
du=max(vu[i2-1],gu[k][j2-1]);
dd=max(vd[i2-1],gd[k][j2-1]);
ds=max(vs[i2-1],gs[k][j2-1]);
ll rez=max(ds,du+dd)+lx+rx;
if (ans>rez)
ans=rez;
}
}
printf("%d\n",ans);
return 0;
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
41 | scanf("%d%d%d",&h,&w,&n);
| ~~~~~^~~~~~~~~~~~~~~~~~~
cultivation.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
44 | scanf("%d%d",&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
