Submission #15236

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15236	2015-07-12T04:21:35 Z	gs14004	달리는 게임 (kriii3_E)	C++14	70 / 70	238 ms	47956 KB

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.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	2 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	15 ms	47956 KB	Output is correct
2	Correct	14 ms	47956 KB	Output is correct
3	Correct	11 ms	47956 KB	Output is correct
4	Correct	27 ms	47956 KB	Output is correct
5	Correct	24 ms	47956 KB	Output is correct
6	Correct	28 ms	47956 KB	Output is correct
7	Correct	115 ms	47956 KB	Output is correct
8	Correct	238 ms	47956 KB	Output is correct
9	Correct	139 ms	47956 KB	Output is correct