fork download 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. using namespace std;
  6. #define re(i, n) for (int i=0; i<n; i++)
  7. #define re1(i, n) for (int i=1; i<=n; i++)
  8. #define re2(i, l, r) for (int i=l; i<r; i++)
  9. #define re3(i, l, r) for (int i=l; i<=r; i++)
  10. #define rre(i, n) for (int i=n-1; i>=0; i--)
  11. #define rre1(i, n) for (int i=n; i>0; i--)
  12. #define rre2(i, r, l) for (int i=r-1; i>=l; i--)
  13. #define rre3(i, r, l) for (int i=r; i>=l; i--)
  14. #define ll long long
  15. const int MAXN = 100010;
  16. const double zero = 1e-7, INF = 1e10, INF0 = 1e20;
  17. struct qnode {
  18.     double x; int No;
  19. } Q[MAXN + 1];
  20. int n, A[MAXN], B[MAXN], front, rear;
  21. ll F[MAXN], res;
  22. void init()
  23. {
  24. 	scanf("%d", &n);
  25. 	re1(i, n) scanf("%d", &A[i]);
  26. 	re1(i, n) scanf("%d", &B[i]);
  27. }
  28. double f01(int a1, ll b1, int a2, ll b2)
  29. {
  30. 	if (a1 == a2) return INF0; else return (double) (b2 - b1) / (a1 - a2);
  31. }
  32. void ins(int z)
  33. {
  34. 	int a0 = A[z + 1]; ll b0 = F[z]; double x1 = 0;
  35. 	if (front <= rear && b0 == F[Q[front].No]) {
  36. 		if (a0 <= A[Q[front].No + 1]) return; else {x1 = Q[front].x; front++;}
  37. 	}
  38. 	double x2, _x; int No0;
  39. 	while (front <= rear) {
  40. 		x2 = Q[front].x; No0 = Q[front].No;
  41. 		_x = f01(a0, b0, A[No0 + 1], F[No0]);
  42. 		if (_x + zero >= x1 && _x + zero < x2) {Q[--front].x = _x; Q[front].No = z; return;} else {x1 = x2; front++;}
  43. 	}
  44. 	Q[--front].x = INF; Q[front].No = z;
  45. }
  46. void solve()
  47. {
  48. 	F[0] = F[1] = 0; front = n; rear = n - 1; ins(0);
  49. 	int l, r, mid;
  50. 	re3(i, 2, n) {
  51. 		l = front; r = rear;
  52. 		while (l < r) {
  53. 			mid = l + r >> 1;
  54. 			if (Q[mid].x + zero >= B[i]) r = mid; else l = mid + 1;
  55. 		}
  56. 		F[i] = F[Q[l].No] + (ll) A[Q[l].No + 1] * B[i];
  57. 		if (F[i - 1] > F[i]) F[i] = F[i - 1];
  58. 		ins(i - 1);
  59. 	}
  60. 	res = F[n];
  61. }
  62. void pri()
  63. {
  64. 	cout << res << endl;
  65. }
  66. int main()
  67. {
  68. 	init();
  69. 	solve();
  70. 	pri();
  71. 	return 0;
  72. }
  73.  
Success #stdin #stdout 0.02s 5416KB
comments (?)
stdin 
4
1 10 5 1
0 0 10 1
stdout 
100
https://ideone.com/P7GzIi
language:
C++ (gcc 8.3)
created:
12 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!