답안 #5421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5421	2014-05-01T12:33:58 Z	gs12006	금 캐기 (IZhO14_divide)	C++	100 / 100	160 ms	8824 KB

divide

#include <stdio.h>
#include <algorithm>
using namespace std;

long long int g[110000],l[110000],e[110000];

struct gw
{
	long long int x,e,w;
}a[220000];

bool cmp(gw x,gw y)
{
	if (x.e-l[x.x]==y.e-l[y.x]) return x.x<y.x;
	return x.e-l[x.x]<y.e-l[y.x]; 
}

int main()
{
	long long int n,i,se=0,ge=0,mini=1<<30,gmax=0;
	gw tgw;
	scanf("%lld",&n);
	for (i=0;i<n;i++)
	{
		scanf("%lld %lld %lld",&l[i+1],&g[i+1],&e[i+1]);
		g[i+1]+=ge;
		ge=g[i+1];
		e[i+1]+=se;
		se=e[i+1];
		tgw.e=e[i];
		tgw.x=i+1;
		tgw.w=0;
		a[2*i]=tgw;
		tgw.e=e[i+1];
		tgw.w=1;
		a[2*i+1]=tgw;
	}
	sort(a,a+2*n,cmp);
	for (i=0;i<2*n;i++)
	{
		if (a[i].w==0)
		{
			if (a[i].x<mini) mini=a[i].x;
		}
		else
		{
			if (g[a[i].x]-g[mini-1]>gmax) gmax=g[a[i].x]-g[mini-1];
		}
	}
	printf("%lld",gmax);
}

Subtask #1

17.0 / 17.0

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

Subtask #2

31.0 / 31.0

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

Subtask #3

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	8824 KB	Output is correct
2	Correct	4 ms	8824 KB	Output is correct
3	Correct	0 ms	8824 KB	Output is correct
4	Correct	24 ms	8824 KB	Output is correct
5	Correct	44 ms	8824 KB	Output is correct
6	Correct	84 ms	8824 KB	Output is correct
7	Correct	68 ms	8824 KB	Output is correct
8	Correct	68 ms	8824 KB	Output is correct
9	Correct	60 ms	8824 KB	Output is correct
10	Correct	152 ms	8824 KB	Output is correct
11	Correct	160 ms	8824 KB	Output is correct
12	Correct	156 ms	8824 KB	Output is correct