I am trying to solve this problem on codeforces using dynamic programming. I have made the recurrence which is of O(N^2) complexity but it is timing out. I know that the complexity of this solution can be reduced to O(N) via Convex hull optimization which is explained here. But I am not able to reduce the complexity. Please help.
This is my code.
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
typedef long long ll;
ll a[MAX],b[MAX],dp[MAX];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
cin >> b[i];
dp[0] = 0;
for(int i = 1; i < n; i++)
{
dp[i] = 1e18;
for(int j = 0; j < i; j++)
{
dp[i] = min(dp[i],dp[j] + a[i] * b[j]);
}
}
cout << dp[n-1];
}