$f(l)$ 表示以时间 $l$ 为起点开始挤奶的最大价值

时间复杂度 $O(n + m)$

#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m, k;
int f[N];
vector<PII> s[N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    while (m -- )
    {
        int l, r, w;
        scanf("%d%d%d", &l, &r, &w);
        s[l].push_back({r, w});
    }

    for (int l = n - 1; ~l; l -- )
    {
        for (auto &[r, w] : s[l])
            f[l] = max(f[l], f[min(r + k, n - 1)] + w);
        f[l] = max(f[l], f[l + 1]);    
    }

    printf("%d\n", f[0]);

    return 0;
}