oj.uz

Submission #5421

# Submission time Handle Problem Language Result Execution time Memory
5421 2014-05-01T12:33:58 Z gs12006 Divide and conquer (IZhO14_divide) C++
100 / 100
 160 ms 8824 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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