oj.uz

Submission #15319

# Submission time Handle Problem Language Result Execution time Memory
15319 2015-07-12T05:56:32 Z ggoh 달리는 게임 (kriii3_E) C++
70 / 70
 256 ms 47956 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
long long a,i,j,sz,m,M,dp[1000006],x[1000006],P[1000006],b[1000006],la[1000006],lb[1000006];
long double cross(long long tt)
{
	return (long double)(lb[tt+1]-lb[tt])/(la[tt]-la[tt+1]);
}
long long search(long long U)
{
	long long p=0,q=sz,h;
	long double u;
	while(p!=q-1)
	{
		h=(p+q)/2;
		u=cross(h-1);
		if(u>U)
		{
			p=h;
		}
		else q=h;
	}
	return U*la[p]+lb[p];
}
void convex(long long xx,long long yy)
{
	la[sz]=xx;
	lb[sz]=yy;
	while(sz>1&&cross(sz-1)>cross(sz-2))
	{
		la[sz-1]=la[sz];
		lb[sz-1]=lb[sz];
		sz--;
	}
	sz++;
}
main()
{
	scanf("%lld",&a);
	for(i=1;i<=a;i++)scanf("%lld",&x[i]);
	for(i=1;i<=a;i++)P[i]=P[i-1]+i*x[i],b[i]=b[i-1]+x[i];
	dp[0]=0;
	convex(0,dp[0]);
	for(i=1;i<=a+1;i++)
	{
		M=search(b[i-1]);
		m=std::max(M+P[i-1],m);
		dp[i]=M+P[i-1]-P[i]+i*b[i];
		convex(-i,dp[i]);
	}
	printf("%lld",m);
}

Subtask #1
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 47956 KB Output is correct
2 Correct 0 ms 47956 KB Output is correct
3 Correct 0 ms 47956 KB Output is correct
4 Correct 0 ms 47956 KB Output is correct
5 Correct 0 ms 47956 KB Output is correct
6 Correct 0 ms 47956 KB Output is correct
7 Correct 0 ms 47956 KB Output is correct
8 Correct 0 ms 47956 KB Output is correct
9 Correct 0 ms 47956 KB Output is correct
10 Correct 0 ms 47956 KB Output is correct
11 Correct 0 ms 47956 KB Output is correct
12 Correct 0 ms 47956 KB Output is correct
13 Correct 0 ms 47956 KB Output is correct
14 Correct 0 ms 47956 KB Output is correct
15 Correct 0 ms 47956 KB Output is correct
16 Correct 0 ms 47956 KB Output is correct
17 Correct 0 ms 47956 KB Output is correct
18 Correct 0 ms 47956 KB Output is correct

Subtask #2
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 47956 KB Output is correct
2 Correct 12 ms 47956 KB Output is correct
3 Correct 7 ms 47956 KB Output is correct
4 Correct 19 ms 47956 KB Output is correct
5 Correct 23 ms 47956 KB Output is correct
6 Correct 29 ms 47956 KB Output is correct
7 Correct 123 ms 47956 KB Output is correct
8 Correct 249 ms 47956 KB Output is correct
9 Correct 256 ms 47956 KB Output is correct