记录编号	573199	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[BZOJ 2726]任务安排3	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	1.815 s
提交时间	2022-07-21 17:52:26	内存使用	11.91 MiB

/*
斜率优化+二分查找  时间复杂度：O(N*logN)  

与 任务安排2(cogs 1162) 一题不同的是，T可能是负数，意味着sumT不再具有单调性，
从而需要最小化截距的直线斜率 S+sumT[i] 不具有单调性。故，不能在单调队列中
只保留凸壳上“ 连接相邻两点的线段斜率 ”大于 S+sumT[i] 的部分，而是必须维护整个凸壳。
这样一来，就不需要在队头把斜率与 S+sumT[i] 比较。

队头也不一定是最优决策，我们可以在单调队列中二分查找，求一个位置 p，p左侧线段斜率比 S+sumT[i] 
小，右侧斜率比 S+sumT[i] 大，p就是最优决策。

队尾维护斜率单调性的方法与 任务安排2 一题相同。
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=300001;

ll n,s,f[N],sumT[N],sumC[N];
ll q[N],l=1,r=1;//队列

int binary_search(int i,int k)
{
	if(l==r) return q[l];
	int L=l,R=r;
	while(L<R)
	{
		int mid = (L+R) / 2;
		if ((f[q[mid+1]]-f[q[mid]]) <= k*(sumC[q[mid+1]]-sumC[q[mid]]))
			L=mid+1;
		else
			R=mid;
	}
	return q[L];
}

int main()
{
	freopen("batch1.in","r",stdin);
	freopen("batch1.out","w",stdout);
	memset(f,0x3f,sizeof(f));
	memset(sumT,0,sizeof(sumT));
	memset(sumC,0,sizeof(sumC));
	memset(q,0,sizeof(q));
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>sumT[i]>>sumC[i];
		sumT[i] += sumT[i-1];//前缀和
		sumC[i] += sumC[i-1];
	}
	f[0]=0;
	q[1]=0;
	for(int i=1;i<=n;i++)
	{//队列维护整个凸壳，通过二分找到最优决策
		//因为 S+sumT[i] 不再具有单调性，故队头不再需要保持单调性的检查
		
		//在队列中二分查找最优决策，执行状态转移，计算f[i];
		int j=binary_search(i,s + sumT[i]);
		f[i]=f[j]-(s+sumT[i])*sumC[j]+sumT[i]*sumC[i]+s*sumC[n];//转移
		
		/*
		把新决策 i 插入队尾,插入之前，若3个决策点j1=q[r-1],j2=q[r],j3=i
		不满足斜率单调递增（不满足下凸性，即 j2 是无用决策），则直接从队尾将
		q[r]出队，继续检查新队尾。
		*/
		while(l<r && (f[q[r]]-f[q[r-1]])*(sumC[i]-sumC[q[r]])>=(f[i]-f[q[r]])*(sumC[q[r]]-sumC[q[r-1]]))
		//斜率不等式两边同乘以原来两斜率分母之积，避免大数除法影响精度。
			r--;
		q[++r]=i;//决策 i 入队
	}
	cout<<f[n]<<endl;
	return 0;
}