比赛 20090916练习赛 评测结果 AAAAAAAAAA
题目名称 任务安排 最终得分 100
用户昵称 belong.zmx 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-09-21 19:13:12
显示代码纯文本
program batch(input,output);
var
 n,s:longint;
 i,j:longint;
 t,y:array[1..5000]of longint;
 dp,f1,f2:array[1..5001]of longint;

begin
 assign(input,'batch.in');
 reset(input);
 readln(n);
 readln(s);
 for i:=1 to n do readln(t[i],y[i]);
 close(input);

 f1[n+1]:=0;
 f2[n+1]:=0;
 dp[n+1]:=0;

 for i:=n downto 1 do
 begin
  f1[i]:=f1[i+1]+t[i];
  f2[i]:=f2[i+1]+y[i];
  dp[i]:=maxlongint;
 end;

 for i:=n downto 1 do
  for j:=i+1 to n+1 do
   if dp[j]+(s+f1[i]-f1[j])*f2[i]<dp[i] then
    dp[i]:=dp[j]+(s+f1[i]-f1[j])*f2[i];

 assign(output,'batch.out');
 rewrite(output);
 writeln(dp[1]);
 close(output);
end.