捞

Upd: 我现在换了个 $O(nk)$ 的写法

被hack数据卡掉了 record

代码放出来，求调

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 10005;
int n, m, k, d[N], last[N], arrive[N], cnt[N], effect[N];
struct node {
	int t, x, y;
} p[M];

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i < n; ++i) scanf("%d", &d[i]);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &p[i].t, &p[i].x, &p[i].y);
		++cnt[p[i].y];
		last[p[i].x] = max(last[p[i].x], p[i].t);
	}
	for (int i = 1; i <= n; ++i)
		arrive[i] = max(arrive[i - 1], last[i - 1]) + d[i - 1];
//	int sum = 0;
//	for (int i = 1; i <= n; ++i) {
//		arrive[i] = sum;
//		sum = max(sum, last[i]);
//		sum += d[i];
//	}
	while (k--) {
		int maxx = 0, pos = 0;
		for (int i = n; i >= 2; --i) {
			if (d[i - 1] == 0) effect[i] = 0;
			else if (arrive[i] <= last[i]) effect[i] = cnt[i];
			else effect[i] = effect[i + 1] + cnt[i];
		}
		for (int i = 1; i <= n; ++i) {
			if (effect[i] > maxx) {
				maxx = effect[i];
				pos = i;
			}
		}
		if (pos == 0) break;
		--d[pos - 1];
		for (int j = pos; j <= n; ++j) {
			arrive[j] = max(last[j - 1], arrive[j - 1]) + d[j - 1];
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; ++i) ans += arrive[p[i].y] - p[i].t;
	printf("%d", ans);
	return 0;
}