记录编号	573180	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2022-07-20 17:19:03	内存使用	1.17 MiB

/*
解法1 时间复杂度:O(N^3) 期望得分:60
f(i,j): 把前 i 个任务分成 j 批执行的最小费用;
f(i,j) = min{ f(k,j-1) + (s*j + sumT[i])*(sumC[i]-sumC[k]) } (0<=k<j)

解法2 时间复杂度:O(N^2) 期望得分：100
本题并没有规定把任务分成多少批，解法1之所以需要批次 j ,是因为需要知道
机器启动了多少次(每次需要启动时间S),从而计算出任务 i 所在批次的完成时刻。

事实上，执行一批任务时，不容易直接得知此前机器启动了几次。但我们知道，
机器因执行该批次而花费的时间S，会累加到之后所有任务的完成时刻上。

设：f(i) 表示把前 i 个任务分成若干批执行的最小费用，状态转移方程为：
f(i) = min{ f(j) + sumT[i] * (sumC[i]-sumC[j]) + S*(sumC[N]-sumC[j]) } (0<=j<j)
在上式中，[j+1,i]范围内的任务在同一批完成，sumT[i]是忽略机器启动时间时，
该批任务的完成时刻。因为该批任务的执行，机器的启动时间S会对第j+1个之后
的所有任务产生影响，故我们需要把这部分补充到费用中。

也就是说，我们没有直接求出每批任务的完成时刻，而是在一批任务“开始”对
后续任务产生影响时，就先把费用累加到答案中。这是一种名为“费用提前计算”
的经典思想。
*/
#include <bits/stdc++.h>
using namespace std;

const int N=5001;

long long n,s,f[N],sumT[N],sumC[N];

int main()
{
	freopen("batch.in","r",stdin);
	freopen("batch.out","w",stdout);
	memset(f,0x3f,sizeof(f));
	memset(sumT,0,sizeof(sumT));
	memset(sumC,0,sizeof(sumC));
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		int t,c;
		cin>>t>>c;
		sumT[i] = sumT[i-1]+t;//前缀和
		sumC[i] = sumC[i-1]+c;
	}
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<i;j++)
		{
			f[i]=min(f[i],f[j]+sumT[i]*(sumC[i]-sumC[j])+s*(sumC[n]-sumC[j]));
		}
	}
	cout<<f[n]<<endl;
	return 0;
}