fork download
copy 
  1. #include <cstdio>
  2. #define MN 1000001
  3. int i, j, n, x[MN], dn, L[MN];
  4. long long A, B, C, f[MN], S[MN];
  5. char buffer[5*MN];
  6. double d[MN];
  7. inline double g(int a) {
  8. 	return (double)(f[i]-f[a]+A*(S[i]*S[i]-S[a]*S[a]))/(2*A*(S[i]-S[a]));
  9. }
  10. int main() {
  11. 	scanf("%d%lld%lld%lld\n",&n,&A,&B,&C);
  12. 	gets(buffer+1);
  13. 	int xn = 1;
  14. 	for (i = 1; buffer[i]; i++) {
  15. 		if (buffer[i] == ' ') xn++;
  16. 		else x[xn] = x[xn]*10+(buffer[i]-'0');
  17. 	}
  18. 	d[dn = 1] = -999999999999;
  19. 	for (i = j = 1; i <= n; i++) {
  20. 		S[i] = S[i-1]+x[i];
  21. 		while (j+1 <= dn && d[j+1] <= S[i]) j++;
  22. 		if (j > dn) j = dn;
  23. 		f[i] = f[L[j]] + A*(S[i]-S[L[j]])*(S[i]-S[L[j]])+C;
  24. 		while (dn >= 2 && g(L[dn]) <= d[dn]) dn--;
  25. 		L[++dn] = i;
  26. 		d[dn] = g(L[dn-1]);
  27. 	}
  28. 	printf("%lld",f[n]+B*S[n]);
  29. }
Success #stdin #stdout 0s 39432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8o0BLI
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!