C++14(g++5.4) 解法, 执行用时: 139ms, 内存消耗: 7544K, 提交时间: 2020-07-02 18:14:52

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=300010;
#define int long long
LL f[N], t[N],c[N];
int q[N];
signed main(int argc, char * argv[]) 
{
	int n,s;
	cin>>n>>s;
	for(int i=1;i<=n;++i){
		cin>>t[i]>>c[i];
		t[i]+=t[i-1];
		c[i]+=c[i-1];
	}
	int hh=0,tt=0;
	for(int i=1;i<=n;++i){
		int l=0,r=tt,k=0;
		while(l<=r){
			int mid=(l+r)/2;
			if( (f[q[mid+1]]-f[q[mid]] ) > (t[i]+s)*(c[q[mid+1]]-c[q[mid]])  ) k=mid,r=mid-1;
			else l=mid+1;
		}
		k=q[k];
		f[i]=f[k]-(t[i]+s)*c[k]+t[i]*c[i]+s*c[n];
		while(hh!=tt&&(double)(f[q[tt]]-f[q[tt-1]]) *(c[i]-c[q[tt-1]])>=(double)(f[i]-f[q[tt-1]])*(c[q[tt]]-c[q[tt-1]])) tt--;
		q[++tt]=i;
	}
	cout<<f[n]<<endl;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 92ms, 内存消耗: 7500K, 提交时间: 2022-11-03 14:57:41

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
ll t[N],c[N],f[N];
int q[N];
int main()
{
	int n,s;
	cin>>n>>s;
	for(int i=1;i<=n;++i){
		int tx,cx;
		scanf("%d%d",&tx,&cx);
		t[i]=t[i-1]+tx;
		c[i]=c[i-1]+cx;
	}
	int hh=0,tt=0;
	q[0]=0;
	for(int i=1;i<=n;++i){
		int l=hh,r=tt;
		while(l<r){
			int m=l+r>>1;
			if(f[q[m+1]]-f[q[m]]>(t[i]+s)*(c[q[m+1]]-c[q[m]])) r=m;
			else l=m+1;
		}
		int j=q[r];
		f[i]=f[j]-(t[i]+s)*c[j]+t[i]*c[i]+s*c[n];
		while(hh<tt&&(double)(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt-1]])>=(double)(f[i]-f[q[tt-1]])*(c[q[tt]]-c[q[tt-1]])) --tt;
		q[++tt]=i;
	}
	cout<<f[n];
	return 0;
}

C++ 解法, 执行用时: 149ms, 内存消耗: 7672K, 提交时间: 2022-02-01 14:42:18

#include<bits/stdc++.h>
using namespace std;
long long sc[300001],st[300001],f[300001],n,s,q[300001],l,r;
int dfs(int l,int r,long long S){
	int res=r;
	while(l<=r){
		int mid=(l+r)>>1; 
		if(f[q[mid+1]]-f[q[mid]]>S*(sc[q[mid+1]]-sc[q[mid]]))r=mid-1,res=mid;
		else l=mid+1;
	}
	return q[res];
}
int main(){
	cin>>n>>s;
	for(int i=1;i<=n;i++)cin>>st[i]>>sc[i],st[i]+=st[i-1],sc[i]+=sc[i-1];
	for(int i=1;i<=n;i++){
		int p=dfs(l,r,st[i]+s);
		f[i]=f[p]+s*(sc[n]-sc[p])+st[i]*(sc[i]-sc[p]);
		while(l<r&&(f[q[r]]-f[q[r-1]])*(sc[i]-sc[q[r]])>=(f[i]-f[q[r]])*(sc[q[r]]-sc[q[r-1]]))r--;
		q[++r]=i;
	}
	cout<<f[n];
}