Tf4lX2 - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;

// Mô tả bài toán (tóm tắt):
// - Cho mảng p[1..n] (giá trị dương) và giới hạn tổng k trên mỗi đoạn liên tiếp.
// - L[r] = chỉ số lớn nhất j < r sao cho tổng p[j+1..r] <= k (tức là đoạn (j+1..r) hợp lệ).
// - Ta cần DP: S[i] = chi phí nhỏ nhất để phân chia prefix [1..i],
//   với chi phí của mỗi đoạn = maximum phần tử trong đoạn.
// - Chuyển tiếp: S[i] = min_{j in [L[i], i-1]} ( S[j] + max(p[j+1..i]) ).
// Mục tiêu: tính S[n]. Nếu có p[i] > k với bất kỳ i thì không có nghiệm.

// Thuật toán trong file này:
// - Sử dụng chiến lược "Divide and Conquer on indices" để tính DP nhanh hơn so với O(n^2).
// - Ý tưởng tổng quát: chia khoảng [l..r] theo mid; giải cho nửa trái rồi sử dụng thông tin
//   từ nửa trái để cập nhật các chuyển tiếp cho nửa phải (các j nằm trong [l..mid], i trong [mid+1..r]).
// - Khi khoảng nhỏ (<= 32) dùng brute-force O(len^2) để tránh overhead.
// - Trong nhánh lớn hơn, ta chuẩn bị các mảng phụ (h, q, k) để truy vấn max và tối ưu
//   việc cập nhật S[i] cho nhiều i cùng lúc; đồng thời gom các đoạn cần cập nhật vào
//   một vector tpls rồi xử lý bằng kỹ thuật "sliding window + min prefix" để giảm chi phí.
// - Độ phức tạp thực nghiệm: gần O(n log n) hoặc O(n log^2 n) tùy data, nhưng rất nhanh
//   với n lớn nhờ cắt giảm tìm kiếm và xử lý hàng loạt (batch).

struct Tp3 {
    int u; // vị trí i ở nửa phải (đích)
    int v; // biên trái của khoảng cần xem (>= l)
    int w; // biên phải của khoảng cần xem (<= mid)
};

// Hàm Dnc: tính và cập nhật S trên đoạn [l..r]
// p: mảng giá trị (1-based)
// S: mảng DP (S[0]=0 ban đầu, S[i] khởi INF)
// L: ràng buộc do tổng phải <= k (L[i] là chỉ số j lớn nhất sao cho j < i và đoạn j+1..i hợp lệ -> trong code là lbound)
void Dnc(int l, int r, const vector<ll> &p, vector<ll> &S, const vector<int> &L) {
    if (l >= r) return;
    // Ngưỡng nhỏ để dùng brute-force (cố định 32 như bản gốc)
    if (r - l <= 32) {
        for (int i = l + 1; i <= r; ++i) {
            ll curMax = p[i];
            for (int j = i - 1; j >= max(l, L[i]); --j) {
                // chuyển tiếp S[i] <- S[j] + max(p[j+1..i])
                S[i] = min(S[i], S[j] + curMax);
                curMax = max(curMax, p[j]);
            }
        }
        return;
    }

    int mid = (l + r) >> 1;
    // Giải đệ quy nửa trái trước để S[j] cho j in [l..mid] đã đúng
    Dnc(l, mid, p, S, L);

    // Ta sẽ xử lý các chuyển tiếp j in [l..mid] -> i in [mid+1..r]
    // Tạo các mảng tạm dựa trên kích thước đoạn
    int len = r - l + 1;
    vector<ll> h(len + 5, 0);    // h[t] ~ suffix max từ mid về trái (dạng: h[mid-j]) trong code gốc
    vector<ll> q(len + 5, INF);  // q[t] ~ prefix min S[j] sao cho ... (dùng trong tính nhanh)
    vector<ll> kk(len + 5, INF); // kk[idx] tương đương k[j-l] trong code gốc

    // Tập các 'tpl' (u,v,w) để xử lý nhóm tối ưu sau khi thu thập
    vector<Tp3> tpls;

    // Chuẩn bị q[]: q[0] = S[mid], q[1..] lần lượt = min(S[j], q[prev]) đi ra trái
    q[0] = S[mid];
    for (int j = mid - 1, t = 1; j >= l; --j, ++t) {
        // t = mid - j
        h[t] = max(h[t - 1], p[j + 1]); // h[t] lưu max của một dạng cố định theo chỉ số trong logic gốc
        q[t] = min(S[j], q[t - 1]);
    }

    // Chuẩn bị kk: kk[idx] = h[mid - j] + S[j] tương tự code gốc
    // Ở đây ta đi qua j từ l..mid để viết vào kk[j-l]
    for (int j = l; j <= mid; ++j) {
        int idx = j - l; // vị trí tương ứng
        // mid - j tương đương t ở trên; nếu mid==j thì mid-j=0
        int t = mid - j;
        kk[idx] = h[t] + S[j];
    }

    // Duyệt i ở nửa phải và cập nhật S[i] bằng hai cách:
    // 1) Dùng maxv1 = max(p[mid+1..i]) và q[...] để cập nhật nhanh: S[i] = min(S[i], maxv1 + q[...])
    // 2) Nếu cần xét nhiều j liên tiếp trong một khoảng [a..b] sẽ push vào tpls để xử lý sau bằng min over kk[].
    int jj = mid;
    ll maxv1 = -INF;
    for (int i = mid + 1; i <= r; ++i) {
        maxv1 = max(maxv1, p[i]);
        // Di chuyển jj trái sao cho maxv1 <= h[mid - jj]
        // (ý nghĩa: tìm vị trí jj lớn nhất thỏa điều kiện)
        while (jj >= l && maxv1 > h[mid - jj]) --jj;

        // Cập nhật nhanh sử dụng q: j phải >= (jj+1) và j <= mid
        int leftBound = max(jj + 1, L[i]);
        if (leftBound <= mid) {
            // q[mid - leftBound] tương ứng giá trị min S[j] trong phạm vi cần
            int idx = mid - leftBound;
            S[i] = min(S[i], maxv1 + q[idx]);
        }

        // Nếu vẫn tồn tại phần j trong [L[i], jj] thì chúng ta cần tính:
        // min_{j in [max(L[i], l) .. jj]} kk[j-l] và dùng để cập nhật S[i]
        if (max(l, L[i]) <= jj) {
            tpls.push_back({i, max(l, L[i]), jj});
        }
    }

    // Nếu có các tpl cần xử lý, ta thực hiện 1 quy trình lấy min động trên kk[]
    if (!tpls.empty()) {
        // Đảo ngược để sắp xếp theo v giảm (giống code gốc xử lý theo thứ tự thuận lợi)
        reverse(tpls.begin(), tpls.end());

        // cl..cr là cửa sổ hiện hành trên chỉ số j (biểu diễn bằng j-l), cw là min kk trong cửa sổ
        int cl = tpls[0].v;            // giá trị j ban đầu (chú ý là chỉ số thực j, không là offset)
        int cr = tpls[0].v - 1;        // khởi cửa sổ rỗng
        ll cw = INF;

        // Hàm tiện: truy xuất kk[offset]
        auto getkk = [&](int j)->ll { return kk[j - l]; };

        for (auto &t : tpls) {
            // mở rộng cửa sổ để bao phủ [t.v .. t.w]
            while (cl > t.v) {
                --cl;
                cw = min(cw, getkk(cl));
            }
            while (cr < t.w) {
                ++cr;
                cw = min(cw, getkk(cr));
            }
            // cập nhật S[t.u] với cw (min kk trên khoảng cần)
            S[t.u] = min(S[t.u], cw);
        }
        // giải phóng
        tpls.clear();
    }

    // Đệ quy nửa phải
    Dnc(mid + 1, r, p, S, L);
}

void solve_one_case() {
    int n;
    ll k;
    if (!(cin >> n >> k)) return;
    vector<ll> p(n + 1);
    for (int i = 1; i <= n; ++i) cin >> p[i];

    // Nếu có phần tử > k thì không thể tạo đoạn chứa phần tử đó (mọi đoạn có max >= phần tử đó > k
    // và tổng đoạn phải <= k -> vô nghiệm theo yêu cầu ban đầu), trả -1.
    for (int i = 1; i <= n; ++i) {
        if (p[i] > k) {
            cout << -1 << '\n';
            return;
        }
    }

    // Tính mảng L: cho mỗi r, tìm l0 sao cho tổng p[l0..r] <= k và nếu thêm p[l0-1] thì vượt
    vector<int> L(n + 1);
    ll sum = 0;
    int lptr = 1;
    for (int r = 1; r <= n; ++r) {
        sum += p[r];
        while (sum > k) {
            sum -= p[lptr++];
        }
        // sau khi điều chỉnh, đoạn [lptr..r] hợp lệ, nghĩa là j = lptr-1 là chỉ số lớn nhất sao cho j < r và j thỏa
        L[r] = lptr - 1; // j chạy từ L[r] đến r-1
    }

    // DP S
    vector<ll> S(n + 1, INF);
    S[0] = 0;

    // Chạy thuật toán D&C để tính S[n]
    Dnc(0, n, p, S, L);

    cout << S[n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    if (!(cin >> T)) return 0;
    while (T--) solve_one_case();
    return 0;
}