// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=305;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
int res=1;
while(n){
if(n&1) res=res*a%mod;
a=a*a%mod;n>>=1;
}
return res;
}
const int iroot=power(3,mod-2);
const int base=101;
int R,C,n,ans=inf;
pii p[maxn];
struct Data{
int a=0,b=0,c=0;
}f[maxn][maxn];
int cur[maxn];
void init(){
for(int l=1;l<=n;l++){
int sz=0;
for(int r=l;r<=n;r++){
int d=p[r].se;
for(int i=1;i<=sz;i++) if(d<cur[i]) swap(d,cur[i]);
cur[++sz]=d;
f[l][r].a=cur[1]-1;
f[l][r].b=C-cur[sz];
for(int i=1;i<sz;i++) f[l][r].c=max(f[l][r].c,cur[i+1]-cur[i]-1);
//cout << l << ' ' << r << ' ' << f[l][r].a << ' ' << f[l][r].b << ' ' << f[l][r].c << '\n';
}
}
}
int num[2*maxn];
Data dd[2*maxn];
void cal(int len){
int sz=0;
for(int i=1,pos=1;i<=n;i++){
while(pos<=n && p[pos].fi<p[i].fi+len+1){
int val=p[pos++].fi;
if(val>num[sz]) num[++sz]=val;
}
int val=p[i].fi+len+1;
if(val>num[sz]) num[++sz]=val;
}
for(int i=1,l=1,r=1;i<=sz;i++){
while(l<=n && !(p[l].fi<=num[i] && num[i]<=p[l].fi+len)) l++;
r=max(r,l);
while(r<=n && p[r].fi<=num[i] && num[i]<=p[r].fi+len) r++;
if(l>n) dd[i]={inf,inf,inf};
else dd[i]=f[l][r-1];
}
deque<pii> a,b,c;
auto add = [&](deque<pii> &dq,pii x){
while(!dq.empty() && dq.back().fi<=x.fi) dq.pop_back();
dq.push_back(x);
};
auto del = [&](deque<pii> &dq,int x){
if(!dq.empty() && dq.front().se<=x) dq.pop_front();
};
auto get = [&](deque<pii> &dq){
if(!dq.empty()) return dq[0].fi;
else return inf;
};
for(int l=1,r=1;l<=sz;l++){
r=max(r,l);
while(r<=sz && num[r]<num[l]+R){
add(a,{dd[r].a,r});
add(b,{dd[r].b,r});
add(c,{dd[r].c,r});
r++;
}
del(a,l);del(b,l);del(c,l);
ans=min(ans,len+max(get(a)+get(b),get(c)));
}
//cout << len << ' ' << ans << '\n';
}
void solve(){
cin >> R >> C >> n;
for(int i=1;i<=n;i++) cin >> p[i].fi >> p[i].se;
sort(p+1,p+n+1);
init();
vector<int> d;
for(int i=1;i<=n;i++){
d.push_back(p[i].fi-1);
d.push_back(R-p[i].fi);
for(int j=i;j<=n;j++){
if(p[i].fi!=p[j].fi) d.push_back(p[j].fi-p[i].fi-1);
d.push_back(p[i].fi-1+R-p[j].fi);
}
}
sort(d.begin(),d.end());
d.erase(unique(d.begin(),d.end()),d.end());
for(auto len:d) cal(len);
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;//cin >> test;
while(test--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
