Submission #1071174

#TimeUsernameProblemLanguageResultExecution timeMemory
1071174ttamxCultivation (JOI17_cultivation)C++17
30 / 100
2053 ms1496 KiB
#pragma GCC optimize("Ofast,unroll-loops") #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]; vector<int> pos; 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]; pos.emplace_back(x[i]); } vector<int> xs; int mxa=0,mxb=0,sum=0; sort(pos.begin(),pos.end()); mxa=pos[0]-1; mxb=r-pos[n-1]; for(int i=1;i<n;i++){ sum=max(sum,pos[i]-pos[i-1]-1); } 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 xl:xs){ if(xl<mxa)continue; for(int xr:xs){ if(xr<mxb)continue; if(xl+xr<sum)continue; if(xl+xr<ans){ ans=min(ans,calc(xl,xr)); } } } 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...