#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
pair<ll, ll> P[303];
ll a[303], S[303], E[303], X[303], dp[303][303], L, U;
int dq[303], n;
ll solve(ll len){
// printf(" solve %lld\n", len);
int sz = 0;
for (int i=1,j=1;i<=n||j<=n;){
ll s = min(a[i], a[j]+len);
while(a[i]==s || a[j]+len==s){
if (a[i]==s) i++;
if (a[j]+len==s) j++;
}
if (j > n) break;
ll e = min(a[i], a[j]+len);
assert(j < i);
if (sz > 0 && X[sz] == dp[j][i-1]) E[sz] = e;
else{
++sz;
S[sz] = s, E[sz] = e, X[sz] = dp[j][i-1];
// printf(" fuck %d %d -> %lld\n", j, i-1, X[sz]);
}
}
// for (int i=1;i<=sz;i++) printf(" (%lld, %lld, %lld)", S[i], E[i], X[i]);
// printf("\n");
ll ret = INF;
for (int i=1,j=1,pl=1,pr=1;i<=sz;i++){
while(pl < pr && dq[pl] < i) pl++;
while(j <= sz && E[j-1]-S[i] < L){
while(pl < pr && X[dq[pr]] <= X[j]) pr--;
dq[pr] = j;
pr++, j++;
}
if (j > sz+1) break;
assert(pl < pr);
ret = min(ret, X[dq[pl]]);
}
return ret + len - 2;
}
int main(){
scanf("%lld %lld", &L, &U);
scanf("%d", &n);
for (int i=1;i<=n;i++) scanf("%lld %lld", &P[i].first, &P[i].second);
sort(P+1, P+n+1);
for (int i=1;i<=n;i++) a[i] = P[i].first;
for (int i=n;i>0;i--){
vector<ll> V;
V.push_back(0);
for (int j=n;j>=i;j--){
V.push_back(P[j].second);
}
V.push_back(U+1);
sort(V.begin(), V.end());
for (int j=1;j<(int)V.size();j++) dp[i][n] = max(dp[i][n], V[j] - V[j-1]);
// printf(" ok %d %d -> %lld\n", i, n, dp[i][n]);
for (int j=n-1;j>=i;j--){
int idx = find(V.begin(), V.end(), P[j+1].second) - V.begin();
V.erase(V.begin() + idx);
dp[i][j] = max(dp[i][j+1], V[idx+1] - V[idx]);
// printf(" ok %d %d -> %lld\n", i, j, dp[i][j]);
}
}
a[0] = 0, a[n+1] = L+1;
ll mn = 0;
for (int i=1;i<=n+1;i++) mn = max(mn, a[i] - a[i-1]);
a[n+1] = INF;
ll ans = INF;
for (ll i=mn;i<=L;i++) ans = min(ans, solve(i));
cout << ans << '\n';
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%lld %lld", &L, &U);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
cultivation.cpp:61:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | for (int i=1;i<=n;i++) scanf("%lld %lld", &P[i].first, &P[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
