#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 tmi[LIM][LIM], tma[LIM][LIM], R, C, n, akt1, akt2, akt3;
vector<pair<ll,ll>>Ci, Di, Ei;
ll solveab(ll a, ll b) {
ll c=0, d=0, cpd=0, lst=1;
while(akt3>0 && Ci[akt3-1].st<=b) --akt3;
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[akt3].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));
vector<pair<ll,ll>>Q;
rep(i, n) {
Q.pb({max(1ll, T[P[i].nd].st-a), T[P[i].nd].st});
for(int j=(int)Q.size()-1; j>0; --j) if(Q[j]<Q[j-1]) swap(Q[j], Q[j-1]);
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});
}
Q.clear();
rep(i, n) {
Q.pb({max(1ll, T[P[n-i-1].nd].st-a), T[P[n-i-1].nd].st});
for(int j=(int)Q.size()-1; j>0; --j) if(Q[j]<Q[j-1]) swap(Q[j], Q[j-1]);
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});
}
ll einf=-1;
rep(xd, 2) {
rep(i, n) rep(j, n) {
tmi[i][j]=R+1;
tma[i][j]=0;
}
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);
}
}
rep(i, n) {
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[j][i]=max(tma[j][i], 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-1]<=0) continue;
else if(tmi[i][j-1]==10*INF || tma[i+1][j]==0) einf=max(einf, abs(P[i].st-P[j].st)-1);
//Ei.pb({10*INF, abs(P[i].st-P[j].st)-1});
else if(tmi[i][j-1]-tma[i+1][j]-2>=0) Ei.pb({tmi[i][j-1]-tma[i+1][j]-2, abs(P[i].st-P[j].st)-1});
}
}
reverse(all(P));
}
Ei.pb({10*INF, einf});
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;
vector<ll>kol;
rep(i, n) {
ll x=R-T[i].st;
if(x>=b && a+x>=apb) kol.pb(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) kol.pb(y);
}
sort(all(kol));
akt1=Ci.size();
akt2=Di.size();
akt3=0;
ll lst=-INF;
for(auto i : kol) if(i!=lst) {
ans=min(ans, solveab(a, i));
lst=i;
}
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
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;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
