結果

提出番号	2408
提出者	kya
言語	C++
提出日時	2020-07-23 12:16:43
問題名	(25)Range of Influence
結果	AC
点数	100%

---

テストケース

ソースコード

#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 noexcept {
		return (node[1]);
	}

	const value_type& operator[] (int i) const {
		return node[i + n];
	}

	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 + 1 < n) segl[l].set_val(r + 1, value + b[r + 1]);
        if (l > 0) 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);
		dp[i][i] = b[i];
        update(i, i, dp[i][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 (high - low > 0) {
            const int mid = ((low + high) >> 1);
            int suml = sum[mid] - sum[l];
            int sumr = sum[r + 1] - sum[mid + 1];
            if (suml >= sumr) high = mid;
            else low = mid + 1;
        }

        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;
}