Submission #5064

#TimeUsernameProblemLanguageResultExecution timeMemory
5064aintaDivide and conquer (IZhO14_divide)C++98
100 / 100
72 ms4992 KiB
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct A{
	long long k;
	int num;
	bool operator <(const A &p)const{
		return k != p.k ? k < p.k : num < p.num;
	}
}w[100010], w2[100010];
long long S[100010], tp, res;
int n, i;
int main()
{
	scanf("%d", &n);
	int x, g, d, pv = n;
	for (i = 1; i <= n; i++){
		scanf("%d%d%d", &x, &g, &d);
		S[i] = S[i - 1] + g;
		w2[i].k = tp - x;
		tp = tp + d;
		w[i].k = tp - x;
		w2[i].num = w[i].num = i;
	}
	sort(w + 1, w + n + 1);
	sort(w2 + 1, w2 + n + 1);
	x = 0;
	for (i = n; i >= 1; i--){
		while (pv && w[pv].k >= w2[i].k){
			if (x < w[pv].num)x = w[pv].num;
			pv--;
		}
		if (x >= w2[i].num){
			res = max(res, S[x] - S[w2[i].num - 1]);
		}
	}
	printf("%lld\n", res);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...