Description
题目大意，就是有n个人，m辆车；从第一辆车开始做，做到第m辆车；每辆车要连续地从第一个工人做到第n个工人，第i个工人做第j辆车要a[i] * b[j]分钟。求生产完所有汽车最少需要多少时间。
Input
第一行输入两个整数：工人数N(1<=N<=100,000)和汽车数M(1<=M<=100,000)。
接下来N行描述每一个工人的Ti(1<=Ti<=10,000)。
接下来M行描述每一台汽车的Fj(1<=Fj<=10,000)。
Output
输出一个数表示最少需要的时间。
Sample Input
输入1：
3 3
2
1
1
2
1
1
输入2：
3 3
2
3
3
2
1
2
输入3：
4 5
3
2
2
2
3
1
2
1
2
Sample Output
输出1：
11
输出2：
29
输出3：
55
Data Constraint
40%的数据满足N,M<=1000。
Hint
样例1： 4分钟后，工人1完成1号汽车的工作，他可以立刻开始生产第2台汽车，但如果这样的话将会不满足条件，因为7分钟后，工人2完成2号汽车的工作，此时3号工人还在生产1号汽车，3号工人并不空闲，所以2号汽车在5分钟后开始生产，3号汽车在7分钟后开始生产。3台汽车全部生产完共花费11分钟。
Solution
一开始打了个暴力，发现可以斜率优化，推推推。。。
我们发现，对于第i辆车到第j辆车的过程要max（b[i] * a[j] - b[i+1] * a[j-1]）（1<=j<=n）
设j>k且j比k更大可得斜率式：
(a[j]-a[k])/(a[j-1]-a[k-1])<b[i+1]/b[i]
Code
#include<cstdio>
#include<algorithm>
#define N 100010
#define ll long long
#define db double
using namespace std;
int n,m,b[N],g[N],tot=0;
ll a[N],sum=0,ans=0;
inline int read()
{
int x=0; char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
db slope(int x,int y) {return (db)(a[x]-a[y])/(a[x-1]-a[y-1]);}
int main()
{
freopen("car.in","r",stdin);
// freopen("car.out","w",stdout);
n=read(),m=read();
for (int i=1;i<=n;i++)
{
a[i]=read()+a[i-1];
while (slope(i,g[tot])>slope(g[tot],g[tot-1]) && tot>1) tot--;
g[++tot]=i;
}
for (int i=1;i<=m;i++) b[i]=read();
for (int i=1,l,r,mid,s;i<=m;i++)
{
l=1,r=tot,s=0;
while (l<=r)
{
mid=l+r>>1;
if (slope(g[mid],g[mid-1])>(db)b[i+1]/b[i]) s=mid,l=mid+1;
else r=mid-1;
}
ans+=b[i]*a[g[s]]-b[i+1]*a[g[s]-1];
}
printf("%lld
",ans);
return 0;
}