oj.uz

Submission #5420

# Submission time Handle Problem Language Result Execution time Memory
5420 2014-05-01T12:32:47 Z gs12006 Divide and conquer (IZhO14_divide) C++
17 / 100
 4 ms 4952 KB 
#include <stdio.h>
#include <algorithm>
using namespace std;

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

struct gw
{
	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()
{
	int n,i,se=0,ge=0,mini=1<<30,gmax=0;
	gw tgw;
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		scanf("%d %d %d",&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("%d",gmax);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4952 KB Output is correct
2 Correct 0 ms 4952 KB Output is correct
3 Correct 0 ms 4952 KB Output is correct
4 Correct 0 ms 4952 KB Output is correct
5 Correct 0 ms 4952 KB Output is correct
6 Correct 0 ms 4952 KB Output is correct
7 Correct 0 ms 4952 KB Output is correct
8 Correct 0 ms 4952 KB Output is correct
9 Correct 0 ms 4952 KB Output is correct
10 Correct 0 ms 4952 KB Output is correct
11 Correct 0 ms 4952 KB Output is correct
12 Correct 0 ms 4952 KB Output is correct

Subtask #2
0.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4952 KB Output is correct
2 Correct 0 ms 4952 KB Output is correct
3 Correct 0 ms 4952 KB Output is correct
4 Correct 0 ms 4952 KB Output is correct
5 Incorrect 0 ms 4952 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4952 KB Output is correct
2 Correct 4 ms 4952 KB Output is correct
3 Incorrect 4 ms 4952 KB Output isn't correct
4 Halted 0 ms 0 KB -