#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
#pragma warning (disable: 4996)
long long N, C, L[200009], D[200009], E[200009], S, A[200009], B[200009], RA[400009], RB[400009];
deque<pair<long long, long long>>deq;
long long pl[200009], pr[200009], maxret, s[3009][3009];
void init() {
for (int i = 1; i <= N; i++) maxret = max(maxret, D[i]);
for (int i = 1; i <= N; i++) {
// 区間 [1, i] の値
long long maxn1 = -1, maxid1 = 0, s1 = 0;
for (int j = 1; j <= i; j++) {
long long val = D[1] + D[j] + s1; if (1 == j) val = 0;
if (maxn1 < val) { maxn1 = val; maxid1 = j; } s1 += L[j];
}
long long maxn2 = 0, s2 = 0;
for (int j = maxid1; j >= 1; j--) {
long long val = D[maxid1] + D[j] + s2; if (maxid1 == j) val = 0; maxn2 = max(maxn2, val);
s2 += L[j - 1];
}
s2 = 0;
for (int j = maxid1; j <= i; j++) {
long long val = D[maxid1] + D[j] + s2; if (maxid1 == j) val = 0; maxn2 = max(maxn2, val);
s2 += L[j];
}
pl[i] = maxn2;
}
for (int i = 1; i <= N; i++) {
// 区間 [i, N] の値
long long maxn1 = -1, maxid1 = 0, s1 = 0;
for (int j = N; j >= i; j--) {
long long val = D[N] + D[j] + s1; if (N == j) val = 0;
if (maxn1 < val) { maxn1 = val; maxid1 = j; } s1 += L[j - 1];
}
long long maxn2 = 0, s2 = 0;
for (int j = maxid1; j >= i; j--) {
long long val = D[maxid1] + D[j] + s2; if (maxid1 == j) val = 0; maxn2 = max(maxn2, val);
s2 += L[j - 1];
}
s2 = 0;
for (int j = maxid1; j <= N; j++) {
long long val = D[maxid1] + D[j] + s2; if (maxid1 == j) val = 0; maxn2 = max(maxn2, val);
s2 += L[j];
}
pr[i] = maxn2;
}
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) s[i][j] = s[i][j - 1] + L[j - 1];
}
}
void right_input(pair<long long, long long> E) {
while (!deq.empty() && deq.back().first < E.first) deq.pop_back();
deq.push_back(E);
}
long long calc(long long sz) {
for (int i = 0; i < sz; i++) { RA[i + 1] = A[i] * 2; RA[i + sz + 1] = RA[i + 1]; RB[i] = B[i] * 2; RB[i + sz] = RB[i]; }
for (int i = 1; i <= (sz << 1); i++) RA[i] += RA[i - 1];
deq.clear();
int pos1 = upper_bound(RA, RA + (sz << 1), S) - RA; pos1--;
for (int i = 1; i <= pos1; i++) right_input(make_pair(RA[i] + RB[i], i));
long long ans = 0;
for (int i = 0; i < sz; i++) {
while (RA[pos1 + 1] < RA[i] + S) {
pos1++;
right_input(make_pair(RA[pos1] + RB[pos1], pos1));
}
if (!deq.empty()) {
while (!deq.empty() && deq.front().second <= i) deq.pop_front();
if (!deq.empty()) ans = max(ans, deq.front().first - RA[i] + RB[i]);
}
}
return ans / 2;
}
long long solve(long long l, long long r) {
// ------------------------ サイクル中の部分
S = 0;
for (int i = l; i <= r - 1; i++) { A[i - l] = L[i]; B[i - l] = D[i]; S += L[i]; }
A[r - l] = C; B[r - l] = D[r]; S += C;
long long e0 = calc(r - l + 1);
long long f1 = 0, t3 = 0; for (int i = 0; i <= r - l; i++) { f1 = max(f1, min(t3, S - t3) + B[i]); t3 += A[i]; }
for (int i = r - 1; i >= l; i--) { A[r - 1 - i] = L[i]; B[r - 1 - i] = D[i + 1]; }
A[r - l] = C; B[r - l] = D[l];
long long e1 = calc(r - l + 1);
long long f2 = 0, t4 = 0; for (int i = 0; i <= r - l; i++) { f2 = max(f2, min(t4, S - t4) + B[i]); t4 += A[i]; }
// ------------------------ それ以外の部分 --------------------------
long long maxn1 = 0, t1 = 0; for (int i = l - 1; i >= 1; i--) { t1 += L[i]; maxn1 = max(maxn1, t1 + D[i]); }
long long maxn2 = 0, t2 = 0; for (int i = r; i <= N - 1; i++) { t2 += L[i]; maxn2 = max(maxn2, t2 + D[i + 1]); }
long long e2 = maxn1 + maxn2 + min(C, s[l][r]);
long long e3 = maxn1 + f1;
long long e4 = maxn2 + f2;
return max({ e0, e1, e2, e3, e4, pl[l], pr[r], maxret });
}
int main() {
scanf("%lld%lld", &N, &C);
for (int i = 1; i <= N - 1; i++) scanf("%lld", &L[i]);
for (int i = 1; i <= N; i++) scanf("%lld", &D[i]);
init();
long long res = (1LL << 60);
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
long long T = solve(i, j);
res = min(res, T);
}
}
cout << res << endl;
return 0;
}
Compilation message
shortcut.cpp:6:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning (disable: 4996)
shortcut.cpp: In function 'int main()':
shortcut.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &N, &C);
~~~~~^~~~~~~~~~~~~~~~~~~~
shortcut.cpp:113:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= N - 1; i++) scanf("%lld", &L[i]);
~~~~~^~~~~~~~~~~~~~~
shortcut.cpp:114:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= N; i++) scanf("%lld", &D[i]);
~~~~~^~~~~~~~~~~~~~~
/tmp/cc5i3awZ.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccHgoQEr.o:shortcut.cpp:(.text.startup+0x0): first defined here
/tmp/cc5i3awZ.o: In function `main':
grader.cpp:(.text.startup+0x10d): undefined reference to `find_shortcut(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int)'
collect2: error: ld returned 1 exit status
