T2 pasture by greens 1s 128M (pasture.cpp)

background
Xiao P is a child who likes playing MC...

describe
Xiao P has n pastures in MC, which are arranged in a line from west to East (numbered with 1... N from west to East), so he is worried: in order to control these n pastures, he needs to establish control stations on some pastures, and only one control station can be established on each pastures, The ranch controlled by each control station is all the ranches from its ranch to the first control station in the West (the ranch where the first control station in the west is not controlled) (if there is no control station in the west, it controls all the ranches in the West). It takes a certain cost to control each ranch (after all, building a road between the control station and the ranch requires resources ~), Moreover, the cost is equal to the number of pastures between it and the control station controlling it (excluding itself, but including the pastures where the control station is located) multiplied by the stocking amount of the pastures. The cost of establishing the control station in the ith pastures is ai, and the stocking amount of each pastures i is bi. Of course, the total cost of small P is the smallest, but the IQ of small P is a little insufficient, so the minimum total cost is calculated by you.

Input format
An integer n in the first line indicates the number of pastures
The second line contains n integers, and the i integer represents ai
The third line includes n integers, and the i integer represents bi

Output format
Only one line, including an integer, represents the minimum cost

sample input
4
2 4 2 4
3 1 4 2

sample output
9

Example explanation
Select pasture 1, 3 and 4 to establish control stations, and the minimum cost is 2 + (2 + 1 * 1) + 4 = 9.

Data scope and agreement
For 10% of data, 1 < = n < = 10
For 30% of data, 1 < = n < = 1000
For 100% data, 1 < = n < = 1000000, 0 < AI, Bi < = 10000

Idea:
Transfer equation: f[i]=f[j]+a[i]+(ll)i*(sum[i-1]-sum[j])-(s[i-1]-s[j])
If you don't understand, just play with your own hands and make a data substitution test
After that, it is found that if the n^2 complexity can not make 100% data, since the equation meets the general law of slope optimization equation, slope optimization is considered

code:

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000010
using namespace std;

ll f[maxn],sum[maxn],s[maxn];

inline ll read()//Read quickly 
{
    char c=getchar();
    ll x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}//There is no need to judge negative deletion to simplify 
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
ll q[maxn];

ll a[maxn],b[maxn];

ll getup(ll j,ll k)
{
	return f[j]+s[j]-(f[k]+s[k]);
}

ll getdone(ll j,ll k)
{
	return sum[j]-sum[k];
}

ll getdp(ll i,ll j)
{
//	cout<<i<<" sgsr "<<j<<'\n';
	return f[i]=f[j]+a[i]+(ll)i*(sum[i-1]-sum[j])-(s[i-1]-s[j]);
//	f[i]=f[q[head]]+a[i]+i*(sum[i-1]-sum[q[head]])-(s[i-1]-s[q[head]]);
}
ll n;
int main()
{
	freopen("pasture.in","r",stdin);
	freopen("pasture.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) 
	{
		b[i]=read();
		sum[i]=sum[i-1]+b[i];
		s[i]=s[i-1]+1ll*i*b[i];
	}
	ll head=1,tail=1;
	q[1]=0;
	for(int i=1;i<=n;i++)//For each i enumeration breakpoint
	{
		while(head<tail&&getup(q[head+1],q[head])
		<=(ll)i*getdone(q[head+1],q[head]))
		head++/*,cout<<1<<" "*/;
//		cout<<'\n';
		f[i]=getdp(i,q[head]);
//		ll j=q[head];
//		f[i]=f[j]+a[i]+i*(sum[i-1]-sum[j])-(s[i-1]-s[j]);
		while(head<tail&&(ll)getup(i,q[tail])*getdone(q[tail],q[tail-1])
		<=(ll)getup(q[tail],q[tail-1])*getdone(i,q[tail]))
		//If the slope of i and tail is smaller than that of tail-1 and tail, the tail is illegal and can be deleted directly
		tail--/*,cout<<2<<" "*/;
//		cout<<'\n';
		
		q[++tail]=i; 
//		cout<<head<<" "<<tail<<'\n';
	} 
	/*int l=1,r=1;
    for(int i=1;i<=n;i++){
		while(l<r&&getup(q[l+1],q[l])<=i*getdone(q[l+1],q[l]))l++;
		f[i]=f[q[l]]+a[i]+i*(sum[i-1]-sum[q[l]])-(s[i-1]-s[q[l]]);
		while(l<r&&getup(q[r],q[r-1])*getdone(i,q[r])>=getup(i,q[r])*getdone(q[r],q[r-1]))r--;
		q[++r]=i;
		cout<<l<<" "<<r<<'\n';
    }*/
	
	cout<<f[n]<<'\n';
	
}