1 条题解
-
0
#include <bits/stdc++.h> const int N=2e5+10; using namespace std; typedef long long ll; bool debug1; int n,l=1,r; int q[N]; ll sum,ans,f[N],w[N],dd[N],d[N],s[N]; bool debug2; double slope(int i,int j){ return 1.0*(s[i]*d[i]-s[j]*d[j])/(s[i]==s[j]?1e-9:s[i]-s[j]); } int main(){ // freopen("data.in","r",stdin); // freopen("my.out","w",stdout); // cout<<((&debug2-&debug1)/1024.0/1024.0)<<endl; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld%lld",&w[i],&dd[i]); s[i]=s[i-1]+w[i]; } for(int i=n;i>=1;i--) d[i]=d[i+1]+dd[i]; for(int i=1;i<=n;i++) sum+=d[i]*w[i]; for(int i=1;i<=n;i++){ while(l<r&&slope(i-1,q[r])>=slope(q[r],q[r-1])) r--; q[++r]=i-1; while(l<r&&slope(q[l+1],q[l])>=d[i]) l++; int j=q[l]; f[i]=sum-(s[j]*d[j]-s[j]*d[i]+s[i]*d[i]); } ans=f[1]; for(int i=1;i<=n;i++) ans=min(ans,f[i]); printf("%lld",ans); return 0; }
- 1
信息
- ID
- 1801
- 时间
- 200ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 38
- 已通过
- 13
- 上传者