#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 303;
struct A {
int gap, cost;
bool operator < (const A& o) const {
return gap > o.gap;
}
};
pair<int, int> a[N];
int s[N], e[N], s2[N], e2[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int r, c;
cin >> r >> c;
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> s[i] >> e[i];
s2[i] = s[i];
e2[i] = e[i];
a[i].first = s[i];
a[i].second = e[i];
}
sort(s2 + 1, s2 + 1 + n);
sort(e2 + 1, e2 + 1 + n);
int mnu = s2[1] - 1;
int mnd = r - s2[n];
int mnv = mnu + mnd;
for (int i = 1;i < n;i++) {
mnv = max(mnv, s2[i + 1] - s2[i] - 1);
}
int mnl = e2[1] - 1;
int mnr = c - e2[n];
int mnh = mnr + mnl;
for (int i = 1;i < n;i++) {
mnh = max(mnh, e2[i + 1] - e2[i] - 1);
}
sort(a + 1, a + 1 + n);
vector<A> e;
// minimum sum need
// cost = max(remaining, mnh)
for (int i = 1;i <= n;i++) {
int mn = c + 1, mx = 0;
int j = i + 1;
for (int j = 1;j < i;j++) {
if (a[i].first == a[j].first) continue;
if (a[j].second <= a[i].second) mx = max(mx, a[j].second);
else mn = min(mn, a[j].second);
}
if (mn != mx && a[i].first != 1)
e.push_back({ a[i].first - 1, mn - mx - 1 }); // to corner
mn = c + 1, mx = 0;
while (a[i].first == a[j].first) j++;
for (int k;j <= n;j = k) {
for (k = j;k <= n && a[j].first == a[k].first;k++) {
if (a[j].first - a[i].first - 1 > 0)
e.push_back({ a[j].first - a[i].first - 1,
mn - mx - 1 });
}
for (k = j;k <= n && a[j].first == a[k].first;k++) {
if (a[k].second <= a[i].second) mx = max(mx, a[k].second);
else mn = min(mn, a[k].second);
}
if (mn == mx) break;
}
if (mn != mx && a[i].first != r)
e.push_back({ r - a[i].first, mn - mx - 1 });
}
ll ans = LLONG_MAX;
sort(e.begin(), e.end());
int cost = 0; // column
int sz = e.size();
for (int i = 0;i < sz;i++) {
//cout << e[i].gap << ' ' << e[i].cost << '\n';
cost = max(cost, e[i].cost);
if (i == sz) {
ans = min(ans, 0ll + max(cost, mnh) + mnv);
}
else {
ans = min(ans, 0ll + max(cost, mnh) + max(e[i + 1].gap, mnv));
}
}
cout << ans << '\n';
return 0;
}
/*
3 2
3 1
2 4
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
