题目不能下载数据,不知道问题在哪,求各位大佬调一下
orz
#include<bits/stdc++.h>
using namespace std;
const int m=22000;
int n,p,q;
double k[m],lk;
long long w[m],d[m],f[m],x[m],y[m],ans=2e9,sum;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p>>q;
for(int j=i;j<=n;j++)w[j]+=p;
for(int j=1;j<=i;j++)d[j]+=q;
}
for(int i=2;i<=n;i++){
f[1]+=(w[i]-w[i-1])*d[i];
}
for(int i=2;i<=n;i++){
f[i]=f[i-1]+w[i-1]*(d[i-1]-d[i])-(w[i]-w[i-1])*d[i];
}
x[1]=w[1],y[1]=f[1],k[1]=-1e3;
p=2;
for(int i=2;i<=n;i++){
int flag=0;
while(flag==0){
lk=(y[p-1]-f[i])*1.0/(x[p-1]-w[i]);
if(lk>0)flag=1;
else if(lk>k[p-1])x[p]=w[i],y[p]=f[i],k[p]=lk,p++,flag=1;
else p--;
}
lk=-d[i];
for(int j=1;j<p;j++){
if(lk<k[j]){
q=j-1;
break;
}
}
sum=y[q]-lk*x[q]-w[i]*d[i];
ans=min(ans,sum);
}
cout<<ans;
}