Submission #15319

#	Time	Username	Problem	Language	Result	Execution time	Memory
15319		ggoh	달리는 게임 (kriii3_E)	C++98	70 / 70	256 ms	47956 KiB

E

#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 / 26
• Subtask 2: 44 / 44