fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <fstream>
  7. #include <stdlib.h>
  8.  
  9. #define rep( i, l, r ) for (int i = l; i <= r; i++)
  10. #define down( i, l, r ) for (int i = l; i >= r; i--)
  11. #define MAX 50009
  12.  
  13. using namespace std;
  14.  
  15. int num[MAX], dl[MAX], s, t, n, l, a;
  16. long long sum[MAX], m, dp[MAX];
  17.  
  18. double g(int a, int b)
  19. {
  20. 	return((dp[a] + sum[a]*sum[a] - dp[b] - sum[b]*sum[b]) / (sum[a] - sum [b]));
  21. }
  22.  
  23. int main()
  24. {
  25. 	scanf("%d%d", &n, &l); 
  26. 	rep(i, 1, n) scanf("%d", &num[i]);
  27. 	sum[0] = 0; rep(i, 1, n) sum[i] = sum[i-1] + num[i] + 1;
  28. 	s = 1; t = 1; dl[1] = 0; dp[0] = 0;
  29. 	rep(i, 1, n)
  30. 	{
  31. 		m = sum[i] - l - 1;
  32. 		while (true)
  33. 		{
  34. 			if (t == s) break;
  35. 			if (2 * m <= g(dl[s], dl[s+1])) break;
  36. 			s++;
  37. 		}
  38. 		a = dl[s];
  39. 		dp[i] = dp[a] + (m - sum[a]) * (m - sum[a]);
  40. 		while (true)
  41. 		{
  42. 			if (t == s) break;
  43. 			if (g(dl[t-1], dl[t]) <= g(dl[t], i)) break;
  44. 			t--;
  45. 		}
  46. 		t++; dl[t] = i;
  47. 	}
  48. 	printf("%lld", dp[n]);
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
5 4
3 4 2 1 4
stdout
copy 
1
https://ideone.com/AucjjB
BZOJ 1010
language:
C++ (gcc 8.3)
created:
10 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!