Submission #5064

#	Time	Username	Problem	Language	Result	Execution time	Memory
5064		ainta	Divide and conquer (IZhO14_divide)	C++98	100 / 100	72 ms	4992 KiB

divide

#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);
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52