比赛 2026.1.8 评测结果 RRRRRRRRRRRRRRRRRRRR
题目名称 区间价值 最终得分 0
用户昵称 xuyuqing 运行时间 0.067 s
代码语言 C++ 内存使用 3.67 MiB
提交时间 2026-01-08 19:50:22
显示代码纯文本

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int N = 114514;

struct range {
	long long l;
	long long r;
	long long w;
	
	const bool operator< (const range other) const {
		return r < other.r;
	}
	
	range (long long l, long long r, long long w) : l (l), r (r), w (w) {}
};

int n;
vector<range> vec;
int rs[N];
long long res[N];
long long maxn[N];

int main () {
	
	freopen ("cover.in", "r", stdin);
	freopen ("cover.out", "w", stdout);
	
	cin >> n;
	vec.emplace_back(0, 0, 0);
	for (int i = 1; i <= n; i++) {
		long long l, r, w;
		cin >> l >> r >> w;
		vec.emplace_back(l, r, w);
	}
	sort (vec.begin(), vec.end());
	for (int i = 1; i <= n; i++) {
		int j = lower_bound (rs + 1, rs + i, vec[i].l) - 1 - rs;
		rs[i] = vec[i].r;
		res[i] = maxn[j] + vec[i].w;
		maxn[i] = max (maxn[i - 1], res[i]);
	}
	cout << maxn[n] << endl;
	
	return 0;
}