oj.uz

Submission #5422

# Submission time Handle Problem Language Result Execution time Memory
5422 2014-05-01T12:35:37 Z gs12006 Divide and conquer (IZhO14_divide) C++
100 / 100
 168 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 4 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 4 ms 8824 KB Output is correct
4 Correct 28 ms 8824 KB Output is correct
5 Correct 36 ms 8824 KB Output is correct
6 Correct 84 ms 8824 KB Output is correct
7 Correct 64 ms 8824 KB Output is correct
8 Correct 68 ms 8824 KB Output is correct
9 Correct 76 ms 8824 KB Output is correct
10 Correct 160 ms 8824 KB Output is correct
11 Correct 160 ms 8824 KB Output is correct
12 Correct 168 ms 8824 KB Output is correct