斜率优化，交叉相乘

#include
     
      #include
      
       using namespace std;int t[1000005],f[1000005];long long F[1000005],G[1000005],Sum[1000005],C[1000005];struct node{	long long k,b;}stack[1000005];double check(node a,node b){	return ((double)a.b-b.b)/(b.k-a.k);}int main(){	int n,S;	scanf("%d%d",&n,&S);	for (int i=1; i<=n; i++){		scanf("%d%d",&t[i],&f[i]);		Sum[i]=Sum[i-1]+t[i];		C[i]=C[i-1]+f[i];	}	int top=0;	for (int i=0; i<=n; i++){		int L=1,R=top;		while (L
       
        >1;			double l,r;			if (mid==1) l=-1ll<<60;			else l=check(stack[mid-1],stack[mid]);			if (mid==top) r=1ll<<60;			else r=check(stack[mid+1],stack[mid]);			if (Sum[i]>=l && Sum[i]<=r){				L=mid;				break;			}			else if (Sum[i]
        
         =2 &&(stack[top].b-stack[top-1].b)*(line.k-stack[top].k)<=						(line.b-stack[top].b)*(stack[top].k-stack[top-1].k))top--;		stack[++top]=line;	}	printf("%lld\n",F[n]);	return 0;}