#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
#define x first
#define y second
ll H, W, N, F[3][305][305];
pair<ll, ll> A[305];
struct Data{
ll l, r, c[3];
};
ll Add[605], Del[605];
ll Solve(ll len){
for(ll i = 0; i <= 2 * N; i++){
Add[i] = Del[i] = 0;
}
vector<ll> Num;
A[N + 1].x = 1e18;
for(ll i = 1, j = 1; j <= N;){
if(A[i].x < A[j].x + len + 1){
Num.push_back(A[i].x);
i++;
} else {
Num.push_back(A[j].x + len + 1);
j++;
}
}
Num.erase(unique(Num.begin(), Num.end()), Num.end());
vector<Data> V(Num.size());
for(ll i = 1, p = 0, q = 0; i <= N; i++){
while(p + 1 < Num.size() && !(Num[p] <= A[i].x && A[i].x < Num[p + 1])) p++;
while(q + 1 < Num.size() && !(Num[q] <= A[i].x + len && A[i].x + len < Num[q + 1])) q++;
Add[p]++; Del[q]++;
}
ll s = 1, e = 0;
for(ll i = 0; i < V.size(); i++){
e += Add[i];
V[i].l = Num[i], V[i].r = (i + 1 == V.size() ? INF : Num[i + 1] - 1);
for(ll j = 0; j < 3; j++) V[i].c[j] = F[j][s][e];
s += Del[i];
}
V.pop_back();
deque<ll> dq[3];
ll Res = 1e18;
for(ll i = 0, j = 0; i < V.size(); i++){
for(ll k = 0; k < 3; k++){
while(!dq[k].empty() && dq[k].front() < i) dq[k].pop_front();
}
while(j < V.size() && V[j].r < V[i].l + H){
for(ll k = 0; k < 3; k++){
while(!dq[k].empty() && V[dq[k].back()].c[k] <= V[j].c[k]) dq[k].pop_back();
dq[k].push_back(j);
}
j++;
}
if(!dq[0].empty() && !dq[1].empty() && !dq[2].empty()){
Res = min(Res, max(V[dq[0].front()].c[0] + V[dq[1].front()].c[1], V[dq[2].front()].c[2]));
}
}
return Res;
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> H >> W >> N;
vector<ll> Cand;
for(ll i = 1; i <= N; i++){
cin >> A[i].x >> A[i].y;
Cand.push_back(A[i].x - 1);
Cand.push_back(H - A[i].x);
}
sort(A + 1, A + N + 1);
for(ll i = 1; i <= N; i++){
set<ll> S;
for(ll j = i; j <= N; j++){
S.insert(A[j].y);
F[0][i][j] = *S.begin() - 1, F[1][i][j] = W - *prev(S.end());
for(auto it = S.begin(); ; it++){
if(next(it) == S.end()) break;
F[2][i][j] = max(F[2][i][j], *next(it) - *it - 1);
}
}
}
ll mn = H - A[N].x + A[1].x - 1;
for(ll i = 2; i <= N; i++){
mn = max(mn, A[i].x - A[i - 1].x - 1);
}
ll Ans = 1e18;
for(ll i = 1; i <= N; i++){
for(ll j = 1; j <= N; j++){
Cand.push_back(A[j].x - A[i].x - 1);
Cand.push_back(A[j].x - 1 + H - A[i].x);
}
}
sort(Cand.begin(), Cand.end());
Cand.erase(unique(Cand.begin(), Cand.end()), Cand.end());
for(auto i : Cand){
if(i < mn) continue;
Ans = min(Ans, i + Solve(i));
}
cout << Ans;
}
Compilation message
cultivation.cpp: In function 'll Solve(ll)':
cultivation.cpp:35:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | while(p + 1 < Num.size() && !(Num[p] <= A[i].x && A[i].x < Num[p + 1])) p++;
| ~~~~~~^~~~~~~~~~~~
cultivation.cpp:36:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while(q + 1 < Num.size() && !(Num[q] <= A[i].x + len && A[i].x + len < Num[q + 1])) q++;
| ~~~~~~^~~~~~~~~~~~
cultivation.cpp:40:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(ll i = 0; i < V.size(); i++){
| ~~^~~~~~~~~~
cultivation.cpp:42:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | V[i].l = Num[i], V[i].r = (i + 1 == V.size() ? INF : Num[i + 1] - 1);
| ~~~~~~^~~~~~~~~~~
cultivation.cpp:49:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(ll i = 0, j = 0; i < V.size(); i++){
| ~~^~~~~~~~~~
cultivation.cpp:53:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while(j < V.size() && V[j].r < V[i].l + H){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
