이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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[3][303], dp[303][303], FUCK[2][303][303], L, U;
int dq[3][303], n;
ll solve(ll 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);
++sz;
S[sz] = s, E[sz] = e;
X[0][sz] = FUCK[0][j][i-1], X[1][sz] = FUCK[1][j][i-1], X[2][sz] = dp[j][i-1];
}
ll ret = INF;
int pl[3] = {1, 1, 1}, pr[3] = {1, 1, 1};
for (int i=1,j=1;i<=sz;i++){
for (int z=0;z<3;z++) while(pl[z] < pr[z] && dq[z][pl[z]] < i) pl[z]++;
while(j <= sz && E[j-1]-S[i] < L){
for (int z=0;z<3;z++){
while(pl[z] < pr[z] && X[z][dq[z][pr[z]-1]] <= X[z][j]) pr[z]--;
dq[z][pr[z]] = j;
pr[z]++;
}
j++;
}
if (j > sz && E[j-1]-S[i] < L) break;
for (int z=0;z<3;z++) assert(pl[z] < pr[z]);
ret = min(ret, max(X[0][dq[0][pl[0]]] + X[1][dq[1][pl[1]]], X[2][dq[2][pl[2]]]));
}
return ret + len - 1;
}
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] - 1);
FUCK[0][i][n] = V[1] - V[0] - 1;
FUCK[1][i][n] = V.back() - (*++V.rbegin()) - 1;
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] - V[idx-1] - 1);
FUCK[0][i][j] = V[1] - V[0] - 1;
FUCK[1][i][j] = V.back() - (*++V.rbegin()) - 1;
}
}
ll mn = 0;
for (int i=2;i<=n;i++) mn = max(mn, a[i] - a[i-1]);
mn = max(mn, (L-a[n]) + a[1]);
a[n+1] = INF;
ll ans = INF;
vector<ll> C = {L};
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
if (a[j]-a[i] >= mn) C.push_back(a[j]-a[i]);
if (a[j]-a[i]+1 >= mn) C.push_back(a[j]-a[i]+1);
if (L-a[j]+a[i] >= mn) C.push_back(L-a[j]+a[i]);
}
}
sort(C.begin(), C.end());
C.erase(unique(C.begin(), C.end()), C.end());
for (auto &x:C) ans = min(ans, solve(x));
cout << ans << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
cultivation.cpp: In function 'int main()':
cultivation.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%lld %lld", &L, &U);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
cultivation.cpp:58:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | for (int i=1;i<=n;i++) scanf("%lld %lld", &P[i].first, &P[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |