Code : Blocking Elements

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e15;

// check returns true if a configuration with cost <= k exists.
bool check(vector<long long> &a, long long k) {
    // Add a sentinel. We will always block the last element.
    a.push_back(0);

    int n = a.size();
    vector<long long> dp(n);
    // dp[i] is the the minimum sum of blocked elements when the i-th element
    // is necessarily blocked.
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        // What is the second last blocked element? Suppose it is at position
        // j.
        dp[i] = inf;
        for (int j = i - 1; j >= 0 && sum <= k; j--) {
            dp[i] = min(dp[i], dp[j] + a[i]);
            sum += a[j];
        }
        // We have exhausted all elements to the left, and the sum is <= k.
        // This means that i-th element can act as the only blocked element.
        if (sum <= k) {
            dp[i] = a[i];
        }
    }

    return dp.back() <= k;
}

void solve(vector<long long> &a) {
    long long sum = accumulate(a.begin(), a.end(), 0LL);
    long long low = 0, high = sum, res = -1;
    while (low <= high) {
        long long mid = (low + high) / 2;
        if (check(a, mid)) {
            res = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e15;

// check returns true if a configuration with cost <= k exists.
bool check(vector<long long> &a, long long k) {
    // Add a sentinel. We will always block the last element.
    a.push_back(0);

    int n = a.size();
    vector<long long> dp(n, -1);
    // dp[i] is the the minimum sum of blocked elements when the i-th element
    // is necessarily blocked.

    function<long long(int)> rec = [&](int i) -> long long {
        if (i < 0) {
            return inf;
        }
        if (dp[i] != -1) {
            return dp[i];
        }

        long long sum = 0;
        // What is the second last blocked element? Suppose it is at position
        // j.
        dp[i] = inf;
        for (int j = i - 1; j >= 0 && sum <= k; j--) {
            dp[i] = min(dp[i], rec(j) + a[i]);
            sum += a[j];
        }
        // We have exhausted all elements to the left, and the sum is <= k.
        // This means that i-th element can act as the only blocked element.
        if (sum <= k) {
            dp[i] = a[i];
        }

        return dp[i];
    };

    return rec(n - 1) <= k;
}

void solve(vector<long long> &a) {
    long long sum = accumulate(a.begin(), a.end(), 0LL);
    long long low = 0, high = sum, res = -1;
    while (low <= high) {
        long long mid = (low + high) / 2;
        if (check(a, mid)) {
            res = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        solve(a);
    }
    return 0;
}