记录编号	586999	评测结果	AAAAAAAAAAAAA
题目名称	[CEOI2004]锯木厂选址	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2024-03-07 12:08:24	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e4+10;
const ll inf = 1e17;
int n;
ll d[N],w[N],v[N],f[N],ans;
ll W(int l,int r){return v[r] - v[l] - w[l] * (d[r] - d[l]);}
void solve(int l,int r,int pl,int pr){
    if(l > r)return;
    int mid = l + r >> 1,p = -1;f[mid] = inf;
    for(int i = pl;i <= min(mid-1,pr);i++)if(v[i] + W(i,mid) < f[mid])f[mid] = v[i] + W(i,mid),p = i;
    solve(l,mid-1,pl,p),solve(mid+1,r,p,pr);
}
int main(){
	freopen("two.in","r",stdin);
    freopen("two.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)scanf("%lld%lld",&w[i],&d[i+1]),w[i] += w[i-1];
    for(int i = 2;i <= n+1;i++)v[i] = v[i-1] + w[i-1] * d[i],d[i] += d[i-1]; 
    solve(2,n,1,n-1);
    ans = inf;
    for(int i = 2;i <= n;i++)ans = min(ans,f[i] + W(i,n+1));
    printf("%lld\n",ans);

	return 0;

}