Submission #999453

#TimeUsernameProblemLanguageResultExecution timeMemory
999453AdamGSCultivation (JOI17_cultivation)C++17
0 / 100
2 ms600 KiB
#include<bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const ll INF=2e9+7; const int LIM=307; pair<ll,ll>T[LIM]; ll R, C, n; vector<pair<ll,ll>>Ci, Di, Ei; ll solveab(ll a, ll b) { ll c=0, d=0, cpd=0, lst=1; ll po=0, ko=Ci.size()-1; while(po<ko) { ll sr=(po+ko)/2; if(Ci[sr].st>b) po=sr+1; else ko=sr; } c=Ci[po].nd; po=0; ko=Di.size()-1; while(po<ko) { ll sr=(po+ko)/2; if(Di[sr].st>b) po=sr+1; else ko=sr; } d=Di[po].nd; po=0; ko=(int)Ei.size()-1; while(po<ko) { ll sr=(po+ko)/2; if(Ei[sr].st<b) po=sr+1; else ko=sr; } if(Ei.size()>0 && Ei[po].st>=b) cpd=max(Ei[po].nd, 0ll); return a+b+max(c+d, cpd); } ll solvea(ll a) { Ci.clear(); Di.clear(); Ei.clear(); vector<pair<ll,ll>>P; rep(i, n) P.pb({T[i].nd, i}); sort(all(P)); rep(i, n) { vector<pair<ll,ll>>Q; rep(j, i+1) Q.pb({max(1ll, T[P[j].nd].st-a), T[P[j].nd].st}); sort(all(Q)); ll ma=1, mi=0; for(auto j : Q) { mi=max(mi, j.st-ma-1); ma=max(ma, j.nd); } mi=max(mi, R-ma); if(Q[0].st!=1) mi=INF; Ci.pb({mi, P[i].st-1}); } rep(i, n) { vector<pair<ll,ll>>Q; rep(j, i+1) Q.pb({max(1ll, T[P[n-j-1].nd].st-a), T[P[n-j-1].nd].st}); sort(all(Q)); ll ma=1, mi=0; for(auto j : Q) { mi=max(mi, j.st-ma-1); ma=max(ma, j.nd); } mi=max(mi, R-ma); if(Q[0].st!=1) mi=INF; Di.pb({mi, C-P[n-i-1].st}); } rep(xd, 2) { rep(j, n) rep(i, j) { if(T[P[i].nd].st<=T[P[j].nd].st) { ll mi=R+1, ma=0; for(int l=i+1; l<j; ++l) { if(T[P[l].nd].st>=T[P[j].nd].st) mi=min(mi, T[P[l].nd].st-a); if(T[P[l].nd].st<=T[P[i].nd].st) ma=max(ma, T[P[l].nd].st); } if(mi<=0) Ei.pb({-1, abs(P[i].st-P[j].st)-1}); else if(mi==10*INF || ma==0) Ei.pb({10*INF, abs(P[i].st-P[j].st)-1}); else Ei.pb({mi-ma-2, abs(P[i].st-P[j].st)-1}); } } reverse(all(P)); } sort(all(Ei)); for(int i=(int)Ei.size()-2; i>=0; --i) Ei[i].nd=max(Ei[i].nd, Ei[i+1].nd); vector<ll>A; rep(i, n) A.pb(T[i].st); sort(all(A)); ll b=R-A[n-1], apb=0; rep(i, n-1) apb=max(apb, A[i+1]-A[i]-1); ll ans=INF; rep(i, n) { ll x=R-T[i].st; if(x>=b && a+x>=apb) ans=min(ans, solveab(a, x)); } rep(i, n) rep(j, i) { ll x=abs(T[i].st-T[j].st)-1; if(x==-1 || x<apb) continue; ll y=x-a; if(y>=b) ans=min(ans, solveab(a, y)); } return ans; } ll solve() { ll ans=INF; rep(i, n) ans=min(ans, solvea(T[i].st-1)); return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> R >> C >> n; rep(i, n) cin >> T[i].st >> T[i].nd; ll ans=INF; rep(i, 4) { ans=min(ans, solve()); rep(j, n) T[j]={C-T[j].nd+1, T[j].st}; swap(R, C); } cout << ans << '\n'; }

Compilation message (stderr)

cultivation.cpp: In function 'll solveab(ll, ll)':
cultivation.cpp:16:23: warning: unused variable 'lst' [-Wunused-variable]
   16 |   ll c=0, d=0, cpd=0, lst=1;
      |                       ^~~
#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...