最下面那个点全是100我怎样可以过吖
查看原帖
最下面那个点全是100我怎样可以过吖
291604
王茗仟楼主2022/10/1 07:22
const int MAXN=3e5;
using namespace std;
int t[MAXN],f[MAXN],sumt[MAXN],sumf[MAXN];
int q[MAXN],l,r;
int dp[MAXN];
int n,s;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*f;
}
int main(){
    n=read();s=read();
    for(int i=1;i<=n;i++){
        t[i]=read();f[i]=read();
        sumt[i]=sumt[i-1]+t[i];
        sumf[i]=sumf[i-1]+f[i];
    }
    memset(dp,0x3f3f3f3f,sizeof(dp));
    dp[0]=0;
    l=1,r=1;
    q[1]=0;
    for(int i=1;i<=n;i++){
        while(l<r&&(dp[q[l+1]]-dp[q[l]])<(sumt[i]+s)*(sumf[q[l+1]]-sumf[q[l]]))l++;
        dp[i]=dp[q[l]]+s*sumf[n]+sumt[i]*sumf[i]-sumf[q[l]]*(sumt[i]+s);
        while(l<r&&(dp[q[r]]-dp[q[r-1]])*(sumf[i]-sumf[q[r]])>(dp[i]-dp[q[r]])*(sumf[q[r]]-sumf[q[r-1]]))r--;
        q[++r]=i;
    }
    cout<<dp[n]<<endl;
    return 0;
}

最下面那个点全是100我怎样可以过吖

2022/10/1 07:22
加载中...