比赛 最近的新题 评测结果 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(){;}