比赛 20090916练习赛 评测结果 AAAAAAWWWW
题目名称 任务安排 最终得分 60
用户昵称 王者自由 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-21 20:06:48
显示代码纯文本
#include <cstdio>
const int MAXN = 5010,
      INF = 0x7ffffff;
int n, s;
int T[MAXN], F[MAXN];
int f[MAXN], f1[MAXN], f2[MAXN];
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);
	for(int i=n; i>0; i--) {
		f1[i] = f1[i+1] + T[i];
		f2[i] = f2[i+1] + F[i];
		f[i] = INF;
	}
	for(int i=n; i>0; i--)
		for(int j=i+1; j<=n+1; j++)
			if(f[i] > f[j] + (s + f1[i] - f1[j])* f2[i])
				f[i] = f[j] + (s + f1[i] - f1[j])* f2[i];
	printf("%d\n", f[1]);
	return 0;
}