比赛 |
最近的新题 |
评测结果 |
AAAAAAA |
题目名称 |
兰迪的私人写真 |
最终得分 |
100 |
用户昵称 |
NVIDIA |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2017-07-01 15:23:29 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 2e9
#define N 20000+10
using namespace std;
int n,sw[N],sd[N],d[N],c[N],f[N],q[N],h=0,t=1;
/*char buf[1<<15],*fs,*ft;
inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int q()
{
int x=0,f=1; char ch=getc();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getc();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getc();}return x*f;
}
char mas[1<<15],*FS=mas,*FT=mas+(1<<15);
#define ot(x) (fs==ft?fwrite(mas,1,1<<15,stdout),*(FS=mas)++=x:*FS++=x)
inline void w(int x)
{
if(x<0) {ot(45);x=-x;}
static char s[15],*b;b=s;
if(!x)*b++=48;
for(;x;*b++=x%10+48,x/=10);
for(;b--!=s;ot(*b));
}*/
inline int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x;}
inline int min(int x,int y){return x<y?x:y;}
inline double WORK(int k1,int k2){return (sw[k2]*sd[k2]-sw[k1]*sd[k1])*1.0/(sw[k2]-sw[k1]);}
inline int DO(){
freopen("EOADcangshu.in","r",stdin);
freopen("EOADcangshu.out","w",stdout);
n=read();
for(int i=1;i<=n;++i)
{
int x=read();d[i]=read();
sw[i]=sw[i-1]+x;
sd[i]=sd[i-1]+d[i-1];
}
sd[n+1]=sd[n]+d[n];sw[n+1]=0;
for(int i=1;i<=n+1;++i) c[i]=c[i-1]+sw[i-1]*d[i-1];
q[++h]=1;
for(int i=2;i<=n;++i)
{
while(h<t&&WORK(q[h],q[h+1])<sd[i]) h++;
f[i]=c[n+1]-sw[q[h]]*(sd[i]-sd[q[h]])-sw[i]*(sd[n+1]-sd[i]);
while(h<t&&WORK(q[t],i)<WORK(q[t-1],q[t])) t--;
q[++t]=i;
}
int ans=inf;
for(int i=2;i<=n;++i) ans=min(ans,f[i]);
printf("%d",ans);
}
int aa=DO();
int main(){;}