// only miss the sun when it starts to snow
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=310,mod=1e9+7;
const ll inf=1e18;
int arr[maxn], a[maxn], b[maxn];
map<int,int> pos, cnt;
void add(int x){
// cout<<"SALAM "<<x<<endl;
if(pos.count(x)){
pos[x]++;
return;
}
auto it=pos.lower_bound(x);
if( it != pos.begin() && it != pos.end() ){
int ln= (it->S) - (prev(it)->S) -1;
if(--cnt[ln] == 0) cnt.erase(ln);
}
if( it != pos.begin() ){
int ln= x - (prev(it)->S) - 1;
cnt[ln]++;
}
if( it != pos.end() ){
int ln= (it->S) - x - 1;
cnt[ln]++;
}
pos[x]++;
}
void rem(int x){
// cout<<"DELETE "<<x<<endl;
if(--pos[x] != 0) return;
pos.erase(x);
auto it=pos.lower_bound(x);
if(it != pos.end() ){
int ln= (it->S) - x - 1;
if( --cnt[ln] == 0 ) cnt.erase(ln);
}
if(it != pos.begin() ){
int ln= x - (prev(it)->S) - 1;
if( --cnt[ln] == 0 ) cnt.erase(ln);
}
if(it != pos.begin() && it != pos.end() ){
int ln= (it->S) - (prev(it)->S) - 1;
cnt[ln]++;
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int N,M,n; cin>>N>>M>>n;
vector<pii> vv;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
a[i]--, b[i]--;
arr[i]=i;
}
sort(arr,arr+n,[](int i,int j){ return a[i]<a[j]; } );
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
vv.PB({a[i],n-1-a[j]});
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i]>a[j]) continue;
for(int k=0;k<n;k++){
if(a[i] - a[j] >= a[k] ) vv.PB({a[k], a[i]-a[j]-a[k]});
}
}
}
sort(vv.begin(), vv.end() );
vv.resize( unique(vv.begin(), vv.end() ) - vv.begin() );
ll ans= ll(N) + ll(M);
for(pii p:vv){
int pta=0, ptb=0, nw=0, mxd=0, mxa=0, mxb=0;
pos.clear(), cnt.clear();
while(pta<n || ptb<n){
int vl=1e9;
if(pta<n) vl=min(vl, a[ arr[pta] ] - p.F);
if(ptb<n) vl=min(vl, a[ arr[ptb] ] + p.S);
vl=max(vl,nw);
if(vl>=n) break;
while( pta<n && a[ arr[pta] ] - p.F <= nw)
add( b[ arr[pta] ] ), pta++;
if( pos.empty() ) goto Hell;
mxa= max(mxa, pos.begin()->F);
mxb= max(mxb, M-1- (pos.rbegin()->F) );
mxd= max(mxd, cnt.rbegin()->F);
while( ptb<n && a[ arr[ptb] ] + p.S <= nw)
rem( b[ arr[ptb] ] ), ptb++;
nw=vl;
}
// cout<<"HEYY "<<p.F<<" "<<p.S<<" "<<mxa<<" "<<mxb<<" "<<mxd<<endl;
ans= min(ans, ll(p.F) + ll(p.S) + ll( max( mxa + mxb, mxd ) ) );
Hell:;
}
return cout<<ans<<endl,0;
}
// Deathly mistakes:
// * Read the problem curfully.
// * Check maxn.
// * Overflows.
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
