답안 #5064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5064	2014-01-30T21:24:16 Z	ainta	금 캐기 (IZhO14_divide)	C++	100 / 100	72 ms	4992 KB

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.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4992 KB	Output is correct
2	Correct	0 ms	4992 KB	Output is correct
3	Correct	0 ms	4992 KB	Output is correct
4	Correct	0 ms	4992 KB	Output is correct
5	Correct	0 ms	4992 KB	Output is correct
6	Correct	0 ms	4992 KB	Output is correct
7	Correct	0 ms	4992 KB	Output is correct
8	Correct	0 ms	4992 KB	Output is correct
9	Correct	0 ms	4992 KB	Output is correct
10	Correct	0 ms	4992 KB	Output is correct
11	Correct	0 ms	4992 KB	Output is correct
12	Correct	0 ms	4992 KB	Output is correct

Subtask #2

31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4992 KB	Output is correct
2	Correct	0 ms	4992 KB	Output is correct
3	Correct	0 ms	4992 KB	Output is correct
4	Correct	0 ms	4992 KB	Output is correct
5	Correct	0 ms	4992 KB	Output is correct
6	Correct	0 ms	4992 KB	Output is correct
7	Correct	0 ms	4992 KB	Output is correct
8	Correct	0 ms	4992 KB	Output is correct
9	Correct	0 ms	4992 KB	Output is correct
10	Correct	0 ms	4992 KB	Output is correct
11	Correct	4 ms	4992 KB	Output is correct
12	Correct	4 ms	4992 KB	Output is correct

Subtask #3

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	4992 KB	Output is correct
2	Correct	4 ms	4992 KB	Output is correct
3	Correct	4 ms	4992 KB	Output is correct
4	Correct	16 ms	4992 KB	Output is correct
5	Correct	20 ms	4992 KB	Output is correct
6	Correct	52 ms	4992 KB	Output is correct
7	Correct	44 ms	4992 KB	Output is correct
8	Correct	32 ms	4992 KB	Output is correct
9	Correct	44 ms	4992 KB	Output is correct
10	Correct	60 ms	4992 KB	Output is correct
11	Correct	72 ms	4992 KB	Output is correct
12	Correct	64 ms	4992 KB	Output is correct