题意

你要制作两道料理，分别需要 $N$ 和 $M$ ($1\le N,M\le 10^6$) 个步骤。制作过程中，每次必须完成完整的一个步骤，且同一个料理的不同步骤必须按顺序进行。制做料理的的过程中不能休息。对于第一种料理，完成第 $i$ 个步骤需要的时间为 $A_i$，如果在前 $S_i$ 分钟完成了这个步骤，则会获得 $P_i$ 点分数 (可能为负数)。对于第二种料理的 $B_i$, $T_i$, $Q_i$ 同理。求最多可能获得的分数。

题解

不妨将制作料理的过程看作在网格图上从 $(0,0)$ 走到 $(N,M)$。对每个 $1\le i\le N$，求出最大的 $Y_i$ 满足 $\mathrm{sumA}_i+\mathrm{sumB}_{Y_i}\le S_i$，则如果点 $(i,Y_i)$ 在路径的左上方或路径上，则会获得 $P_i$ 点分数。同理，对于所有的 $1\le j\le M$，求出对应的 $X_j$，则如果点 $(X_j,j)$ 在路径的右下方或路径上，则会获得 $Q_j$ 点分数。不妨将第一类点改为 $(i-1,Y_i+1)$，分数改为 $-P_i$，并将 $P_i$ 直接加入答案。则问题转化为了找到一条路径，使得路径右下方或路径上的点分数的和最大。一个简单的 dp 如下： $$ f(x,y)=\max\{f(x,y-1), f(x-1,y)+s(x-1,y)\} $$ 其中， $s(x,y)$ 表示在 $(x,y)$ 下方的所有点分数的和。容易发现，dp 的过程其实是在加入点的时候在后缀做一个加法，然后求前缀最大值。不妨维护前缀最大值的差分，先加入所有点权非负的点，然后加入点权为负的点，假设其分数为 $-V$，则它会使得后面连续的一段总和最多为 $V$ 的数清零 (最后所有数都为 $0$ 或有一个数只被减去了一部分)。这个过程可以直接用 std::set 维护。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<long long> a(n + 1), b(m + 1), s(n), t(m);
    std::vector<int> p(n), q(m);
    for (int i = 0; i < n; ++i) std::cin >> a[i + 1] >> s[i] >> p[i];
    for (int i = 0; i < m; ++i) std::cin >> b[i + 1] >> t[i] >> q[i];
    for (int i = 1; i <= n; ++i) a[i] += a[i - 1];
    for (int i = 1; i <= m; ++i) b[i] += b[i - 1];
    long long ans = 0;
    std::vector<std::vector<std::pair<int, int>>> pts(n);
    auto addPoint = [&](int x, int y, int v) {
        if (x < 0 || y > m) {
            return;
        } else if (x == n || y == 0) {
            ans += v;
        } else {
            pts[x].emplace_back(y, v);
        }
    };
    for (int i = 1; i <= n; ++i) {
        int y = std::upper_bound(b.begin(), b.end(), s[i - 1] - a[i]) - b.begin() - 1;
        ans += p[i - 1];
        addPoint(i - 1, y + 1, -p[i - 1]);
    }
    for (int i = 1; i <= m; ++i) {
        int x = std::upper_bound(a.begin(), a.end(), t[i - 1] - b[i]) - a.begin() - 1;
        addPoint(x, i, q[i - 1]);
    }
    std::map<int, long long> mp;
    for (int i = 0; i < n; ++i) {
        std::sort(pts[i].begin(), pts[i].end(), std::greater<>());
        for (auto [y, v] : pts[i]) {
            if (v > 0) {
                mp[y] += v;
            } else {
                v = -v;
                auto it = mp.lower_bound(y);
                while (v > 0 && it != mp.end()) {
                    if (v >= it->second) {
                        v -= it->second;
                        it = mp.erase(it);
                    } else {
                        it->second -= v;
                        break;
                    }
                }
            }
        }
    }
    for (auto [y, v] : mp) ans += v;
    std::cout << ans << "\n";
    return 0;
}