\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Quy hoạch động>}}\)

Với mỗi vị trí i thì ta duyệt tất cả vị trí j ≤ i, sao cho tổng trọng lượng và độ cao của đoạn j-i không vượt quá P và Q, sau đó ta dùng cây IT để lấy độ cao lớn nhất của đoạn. \(dp[j-1]+getdocao(j,i)\) sẽ là kết quả.

Độ phức tạp thời gian tổng thể của cách này sẽ là \(O(n^2 * log(n))\)

\(\color{#300000}{\text{Hint 2 <Quy hoạch động + Cải tiến>}}\)

Ta có thể duyệt j từ i-1 giảm dần đến 1 để lấy max độ cao, khi đó ta sẽ không cần dùng cây IT nữa.

Độ phức tạp thời gian tổng thể của cách này sẽ là \(O(n^2)\)

#include <bits/stdc++.h>

using namespace std;
const int N = 1e4 + 2;
int h[N],T[4*N];
long long c[N],w[N],dp[N],P,Q;
int n;
int main()
{
    //freopen("boxstatistics.inp","r",stdin);
    //freopen("boxstatistics.out","w",stdout);
    cin >> n >> P >> Q;
    for (int i = 1; i <= n; i++) cin >> c[i] >> w[i] >> h[i];
    for (int i = 1; i <= n; i++) // prefix_sum
    {
        w[i] = w[i - 1] + w[i];
        c[i] = c[i - 1] + c[i];
    }
    fill(dp + 1,dp + 1 + n,1e18);
    for (int i = 1; i <= n; i++)
    {
        int tmp = 0;
        for (int j = i - 1; j >= 0; j--)
        {
            tmp = max(tmp,h[j + 1]);
            if (c[i] - c[j] <= P && w[i] - w[j] <= Q) dp[i] = min(dp[i],dp[j] + tmp);
            else break;
        }
    }
    cout << dp[n];
    return 0;
}