打的李超线段树。

P5785 过了，但 P2365 和本题都没过。

#include<bits/stdc++.h>
#define int long long
#define ls(p) tree[p].ls
#define rs(p) tree[p].rs
using namespace std;
const int N=1e6+7;
const int MAXN=1e10;
int n,s;
int t[N],c[N];
struct Line
{
	int k,b;
}line[N];
struct Tree
{
	int ls,rs,id;
}tree[N];
int root;
int cnt;
struct Seg_Tree
{
	inline __int128 calc(int id,int x){return (__int128)x*(__int128)line[id].k+(__int128)line[id].b;}
	inline bool cmp(int x,int now,int add){return calc(now,x)>calc(add,x);}
	inline void insert(int &p,int l,int r,int id)
	{
		if(!p) p=++cnt;
		int mid=l+r>>1;
		if(!tree[p].id)
		{
			tree[p].id=id;
			return;
		}
		if(cmp(l,tree[p].id,id)&&cmp(r,tree[p].id,id))
		{
			tree[p].id=id;
			return;
		}
		if(l==r)
		{
			if(cmp(l,tree[p].id,id))
				tree[p].id=id;
			return;
		}
		if(cmp(mid,tree[p].id,id)) swap(tree[p].id,id);
		if(cmp(l,tree[p].id,id)) insert(ls(p),l,mid,id);
		if(cmp(r,tree[p].id,id)) insert(rs(p),mid+1,r,id);
	}
	inline int query(int p,int l,int r,int x)
	{
		int res=calc(tree[p].id,x);
		if(l==r) return res;
		int mid=l+r>>1;
		if(mid>=x) res=min(res,query(ls(p),l,mid,x));
		if(mid<x) res=min(res,query(rs(p),mid+1,r,x));
		return res;
	}
}seg;
int f[N];
signed main()
{
	scanf("%lld %lld",&n,&s);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&t[i],&c[i]);
		t[i]+=t[i-1];
		c[i]+=c[i-1];
	}
	f[1]=t[1]*c[1]+s*c[n];
	line[1]={c[0],f[1]};
	seg.insert(root,0,MAXN,1);
	for(int i=2;i<=n;i++)
	{
		f[i]=seg.query(root,0,MAXN,s+t[i])+t[i]*c[i]+s*c[n];
		line[i]={-c[i],f[i]};
		seg.insert(root,0,MAXN,i);
	}
//	for(int i=1;i<=n;i++)
//	{
//		cout<<f[i]<<" ";
//	}
//	puts("");
//	for(int i=1;i<=n;i++)
//	{
//		cout<<"y="<<line[i].k<<"x+"<<line[i].b<<endl; 
//	}
	printf("%lld\n",f[n]);
}