Submission #1071160

#TimeUsernameProblemLanguageResultExecution timeMemory
1071160ttamxCultivation (JOI17_cultivation)C++17
0 / 100
0 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 calc(int xl,int xr){ vector<int> xs; for(int i=0;i<n;i++){ xs.emplace_back(max(1,x[i]-xl)); xs.emplace_back(min(r,x[i]+xr)+1); } xs.emplace_back(1); xs.emplace_back(r+1); 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(1,x[i]-xl))-xs.begin(); int xj=lower_bound(xs.begin(),xs.end(),min(r,x[i]+xr)+1)-xs.begin(); 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()-1); mxb=max(mxb,c-*pts.rbegin()); if(!dif.empty()){ sum=max(sum,*dif.rbegin()-1); } } return min((long long)INF,(long long)xl+xr+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]; } 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 l=0,r=xs.size()-1;l<n;l++){ int cur=calc(xs[l],xs[r]); ans=min(ans,cur); while(r>0){ int nxt=calc(xs[l],xs[r-1]); if(nxt>=cur)break; r--; cur=nxt; ans=min(ans,cur); } } 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...