#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int N = 307, inf = 2e9;
int n, m, k;
int a[N], b[N];
int mem[2*N][N];
pii gr[2*N][N];
vector <int> add[2*N], rem[2*N];
int main () {
FIO;
cin >> n >> m >> k;
vector <pii> so;
for (int i = 0; i < k; i++) {
cin >> a[i] >> b[i];
a[i]--; b[i]--;
so.pb({a[i], b[i]});
}
sort(all(so));
for (int i = 0; i < k; i++) {
a[i] = so[i].F;
b[i] = so[i].S;
}
vector <int> v, po;
int d = a[0];
for (int i = 0; i < k; i++) a[i] -= d;
d = n-a[k-1]-1;
for (int i = 1; i < k; i++) d = max(d, a[i]-a[i-1]-1);
a[k] = n-1;
for (int i = 0; i <= k; i++) {
for (int j = i; j <= k; j++) {
if (a[j]-a[i] >= d) v.pb(a[j]-a[i]);
if (a[j]-a[i]-1 >= d) v.pb(a[j]-a[i]-1);
}
if (n-a[i]-1 >= d) v.pb(n-a[i]-1);
}
v.pb(d);
sort(all(v)); v.erase(unique(all(v)), v.end());
for (int i = 0; i < k; i++) {
if (a[i]) po.pb(a[i]-1);
po.pb(a[i]);
}
po.pb(m-1);
sort(all(po)); po.erase(unique(all(po)), po.end());
for (int i = 0; i < 2*N; i++) for (int j = 0; j < N; j++) mem[i][j] = inf;
for (int i = 0; i < po.size(); i++) {
set <int> s;
multiset <int> rj;
int o = k-1;
for (int j = 0; j < k; j++) if (a[j] > po[i]) {
o = j-1;
break;
}
rj.insert(0);
for (int j = o; j >= 0; j--) {
mem[i][j] = mem[i][j+1];
gr[i][j].F = gr[i][j+1].F;
gr[i][j].S = gr[i][j+1].S;
if (s.find(b[j]) != s.end()) continue;
auto p1 = s.lower_bound(b[j]);
if (p1 == s.end()) {
if (!s.empty()) rj.insert(b[j]-*s.rbegin()-1);
s.insert(b[j]);
gr[i][j].F = *s.begin();
gr[i][j].S = m-*s.rbegin()-1;
}
else if (p1 == s.begin()) {
rj.insert(*s.begin()-b[j]-1);
s.insert(b[j]);
gr[i][j].F = *s.begin();
gr[i][j].S = m-*s.rbegin()-1;
}
else {
int x = *p1; --p1; int y = *p1;
rj.erase(rj.find(x-y+1));
rj.insert(x-b[j]+1);
rj.insert(b[j]-y+1);
}
mem[i][j] = *rj.rbegin();
}
}
int mn = inf, la = po.size()-1;
for (auto x : v) {
for (int i = 0, j = 0; i < k; i++) {
while (j < po.size() && po[j] < a[i]) j++;
add[j].pb(i);
}
for (int i = 0, j = 0; i < k; i++) {
while (j < po.size() && po[j] < a[i]+x) j++;
rem[j].pb(i);
}
queue <int> q;
int z;
vector <int> v1, v2, v3;
for (int i = 0; i < po.size(); i++) {
for (auto y : add[i]) q.push(y);
z = q.front();
v1.pb(mem[i][z]);
v2.pb(gr[i][z].F);
v3.pb(gr[i][z].S);
if (i != la) for (auto y : rem[i]) q.pop();
add[i].clear();
rem[i].clear();
}
z = q.front();
int mx = v1.back(), mxa = v2.back(), mxb = v3.back();
for (int i = po.size()-2; i >= 0; i--) {
v1[i] = max(v1[i], v1[i+1]);
v2[i] = max(v2[i], v2[i+1]);
v3[i] = max(v3[i], v3[i+1]);
}
int re = inf;
for (int i = 0; i < po.size(); i++) {
while (po[i]+n-1 > a[z]+x) {
z++;
if (z == k) break;
mx = max(mx, mem[la][z]);
mxa = max(mxa, gr[la][z].F);
mxb = max(mxb, gr[la][z].S);
}
if (z == k) break;
re = min(re, max(max(mx, v1[i]), max(mxa, v2[i]) + max(mxb, v3[i])));
}
mn = min(mn, re+x);
}
cout << mn << "\n";
return 0;
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i = 0; i < po.size(); i++) {
| ~~^~~~~~~~~~~
cultivation.cpp:101:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | while (j < po.size() && po[j] < a[i]) j++;
| ~~^~~~~~~~~~~
cultivation.cpp:105:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | while (j < po.size() && po[j] < a[i]+x) j++;
| ~~^~~~~~~~~~~
cultivation.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < po.size(); i++) {
| ~~^~~~~~~~~~~
cultivation.cpp:117:27: warning: unused variable 'y' [-Wunused-variable]
117 | if (i != la) for (auto y : rem[i]) q.pop();
| ^
cultivation.cpp:129:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 0; i < po.size(); i++) {
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
4676 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
4676 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
4676 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Runtime error |
2 ms |
4676 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
