Submission #15236

#	Time	Username	Problem	Language	Result	Execution time	Memory
15236		gs14004	달리는 게임 (kriii3_E)	C++14	70 / 70	238 ms	47956 KiB

E

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long lint;

int n;
lint dp[1000005];
lint a[1000005];
lint s1[1000005];
lint s2[1000005];

struct cht{
	lint pa[1000005], pb[1000005];
	int sz, piv;
	double cross(int a, int b){
		return 1.0 * (pb[a] - pb[b]) / (pa[b] - pa[a]);
	}
	void add(lint a, lint b){
		pa[sz] = a;
		pb[sz] = b;
		while(sz - 2 >= 0 && cross(sz-2,sz-1) > cross(sz-1,sz)){
			pa[sz-1] = pa[sz];
			pb[sz-1] = pb[sz];
			sz--;
		}
		sz++;
	}
	lint query(lint piv){
		int s = 0, e = sz - 1;
		while(s != e){
			int m = (s+e)/2;
			if(cross(m,m+1) <= piv) s = m+1;
			else e = m;
		}
		return pa[s] * piv + pb[s];
	}
}cht;

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%lld",&a[i]);
		s1[i] = s1[i-1] + a[i];
		s2[i+1] = s2[i] + s1[i];
	}
	cht.add(0,0);
	for(int i=1; i<=n; i++){
		dp[i] = cht.query(-s1[i]) + s1[i] * i - s2[i];
		dp[i] = max(dp[i-1], dp[i]);
		cht.add(i, s2[i] + dp[i]);
	}
	printf("%lld",dp[n]);
}

• Subtask 1: 26 / 26
• Subtask 2: 44 / 44