| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 999457 | AdamGS | Cultivation (JOI17_cultivation) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, tmi[LIM][LIM], tma[LIM][LIM];
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(i, n) rep(j, n) tma[i][j]=0;
rep(i, n) rep(j, n) tmi[i][j]=R+1;
rep(i, n) {
for(int j=i+1; j<n; ++j) {
tmi[i][j]=tmi[i][j-1];
if(T[P[j].nd].st>=T[P[i].nd].st) tmi[i][j]=min(tmi[i][j], T[P[j].nd].st-a);
}
for(int j=i-1; j>=0; --j) {
tma[j][i]=tma[j+1][i];
if(T[P[j].nd].st<=T[P[i].nd].st) tma[i][j]=max(tma[i][j], T[P[j].nd].st);
}
}
rep(j, n) rep(i, j) {
if(T[P[i].nd].st<=T[P[j].nd].st) {
if(tmi[i][j]<=0) Ei.pb({-1, abs(P[i].st-P[j].st)-1});
else if(tmi[i][j]==10*INF || ma==0) Ei.pb({10*INF, abs(P[i].st-P[j].st)-1});
else Ei.pb({tmi[i][j]-tma[i][j]-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';
}