Submission #1071233

#TimeUsernameProblemLanguageResultExecution timeMemory
1071233ttamxCultivation (JOI17_cultivation)C++17
0 / 100
1 ms348 KiB
#include<bits/stdc++.h> using namespace std; const int N=305; const int INF=2e9; int n; int r,c; int x[N],y[N]; int gx,gy; int calc(int dx){ vector<int> xs; for(int i=0;i<n;i++){ if(x[i]+dx<gx)return INF; xs.emplace_back(max(x[i],gx)); xs.emplace_back(min(x[i]+dx,gx+r-1)+1); } xs.emplace_back(gx); xs.emplace_back(gx+r); sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); int xn=xs.size(); vector<vector<pair<int,int>>> event(xn); for(int i=0;i<n;i++){ int xi=lower_bound(xs.begin(),xs.end(),max(x[i],gx))-xs.begin(); int xj=lower_bound(xs.begin(),xs.end(),min(x[i]+dx,gx+r-1)+1)-xs.begin(); assert(xi<xj); event[xi].emplace_back(y[i],1); event[xj].emplace_back(y[i],0); } event.pop_back(); int mxa=0,mxb=0,sum=0; multiset<int> pts,dif; for(auto &e:event){ for(auto [x,t]:e){ if(t){ auto it=pts.emplace(x); if(next(it)!=pts.end()&&it!=pts.begin()){ dif.erase(dif.find(*next(it)-*prev(it))); } if(next(it)!=pts.end()){ dif.emplace(*next(it)-*it); } if(it!=pts.begin()){ dif.emplace(*it-*prev(it)); } }else{ auto it=pts.find(x); assert(it!=pts.end()); if(next(it)!=pts.end()){ dif.erase(dif.find(*next(it)-*it)); } if(it!=pts.begin()){ dif.erase(dif.find(*it-*prev(it))); } if(next(it)!=pts.end()&&it!=pts.begin()){ dif.emplace(*next(it)-*prev(it)); } pts.erase(it); } } if(pts.empty())return INF; mxa=max(mxa,*pts.begin()-gy); mxb=max(mxb,gy+c-1-*pts.rbegin()); if(!dif.empty()){ sum=max(sum,*dif.rbegin()-1); } } return min(INF,dx+max(sum,mxa+mxb)); } int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> r >> c >> n; for(int i=0;i<n;i++){ cin >> x[i] >> y[i]; } pair<int,int> px(INF,INF),py(INF,INF); for(int i=0;i<n;i++){ px=min(px,{x[i],y[i]}); py=min(py,{y[i],x[i]}); } gx=py.second; gy=px.second; vector<int> xs; for(int i=0;i<n;i++){ xs.emplace_back(x[i]-1); xs.emplace_back(r-x[i]); for(int j=0;j<n;j++){ int d=abs(x[i]-x[j]); xs.emplace_back(d); if(d>0){ xs.emplace_back(d-1); } } } sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); int ans=r+c-2; for(int dx:xs){ ans=min(ans,calc(dx)); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...