记录编号	344090	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-11-09 21:06:18	内存使用	0.31 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 5005;
int N, S, T[maxn], F[maxn];
int f[maxn], q[maxn], hd, tl;
#define h(i) T[i]
#define x(j) F[j-1]
#define y(j) (f[j-1]-T[j-1]*(F[N]-F[j-1])-S*F[j-1])
#define P(j1, j2) (1.0*(y(j2)-y(j1))/(x(j2)-x(j1)))
int main() {
	freopen("batch.in","r",stdin); freopen("batch.out","w",stdout);
	scanf("%d%d", &N, &S);
	for(int i=1; i<=N; ++i) {
		scanf("%d%d", T+i, F+i);
		T[i] += T[i-1];
		F[i] += F[i-1];
	}
#define Hd q[hd]
	for(int i=1; i<=N; ++i) {
		while(hd+1<tl && P(q[tl-2], q[tl-1]) > P(q[tl-1], i)) --tl;
		q[tl++] = i;
		while(hd+1<tl && P(q[hd], q[hd+1]) < h(i)) ++hd;
		f[i] = f[Hd-1]+(F[N]-F[Hd-1])*(S+T[i]-T[Hd-1]);
	}
	printf("%d\n", f[N]);
	getchar(), getchar();
	return 0;
}