ソースコード
#include <vector>
#include <functional>
template<class T>
struct segment_tree {
using value_type = T;
using F = std::function<T(T, T)>;
private :
int n;
const F f;
const value_type ie;
std::vector<value_type> node;
public :
segment_tree () { }
segment_tree (const F &f, const value_type &ie) : f(f), ie(ie) { }
void assign (int _n) noexcept {
n = 1;
while (n < _n) n <<= 1;
node.assign(2 * n, ie);
}
void assign (int _n, const value_type &x) noexcept {
assign(_n);
std::fill(node.begin() + n, node.end(), x);
for (int i = n; i--> 0;) {
node[i] = f(node[i << 1 | 0], node[i << 1 | 1]);
}
}
template<class Iterator>
void build (Iterator l, Iterator r) {
assign(r - l);
for (int i = n; l != r; i++, l++) node[i] = *l;
for (int i = n; i--> 0;) {
node[i] = f(node[i << 1 | 0], node[i << 1 | 1]);
}
}
void set_val (int i, const value_type &x) {
i += n;
node[i] = x;
for (i >>= 1; i > 0; i >>= 1) {
node[i] = f(node[i << 1 | 0], node[i << 1 | 1]);
}
}
constexpr value_type fold (int l, int r) {
value_type vl = ie, vr = ie;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) vl = f(vl, node[l++]);
if (r & 1) vr = f(node[--r], vr);
}
return f(vl, vr);
};
constexpr const value_type& fold_all() const {
return (node[1]);
}
constexpr const value_type& operator[] (int i) const {
return node[i + n];
}
constexpr const value_type& at (int i) const {
return node.at(i + n);
}
};
#include <iostream>
#include <vector>
#include <functional>
constexpr int INF = (1 << 30);
int main() {
int n;
std::cin >> n;
std::vector<int> a(n), b(n), sum(n + 1, 0);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
sum[i + 1] = sum[i] + a[i];
}
for (int i = 0; i < n; i++) {
std::cin >> b[i];
}
std::vector<std::vector<int>> dp(n, std::vector<int>(n, INF));
std::vector<segment_tree<int>> segl(n, segment_tree<int>([](int a, int b) { return std::min(a, b); }, INF));
std::vector<segment_tree<int>> segr(n, segment_tree<int>([](int a, int b) { return std::min(a, b); }, INF));
std::function<void(int, int, int)> update = [&] (int l, int r, int value) -> void {
if (r > l) return;
if (r + 1 < n) segl[l].set_val(r + 1, value + b[r + 1]);
if (0 < l) segr[r].set_val(l - 1, value + b[l - 1]);
};
for (int i = 0; i < n; i++) {
segl[i].assign(n);
segr[i].assign(n);
update(i, i, b[i]);
}
for (int d = 1; d < n; d++) for (int l = 0; l + d < n; l++) {
const int r = l + d;
int low = l, high = r + 1;
while (std::abs(high - low) > 1) {
const int mid = ((low + high) >> 1);
if(sum[mid] - sum[l] >= sum[r + 1] - sum[mid]) high = mid;
else low = mid;
}
low++;
dp[l][r] = std::min(segl[l].fold(low, r + 1), segr[r].fold(l, low));
update(l, r, dp[l][r]);
}
std::cout << dp[0][n - 1] << '\n';
return 0;
}