比赛 noip20081103 评测结果 AAAATTTTTW
题目名称 奶酪工厂 最终得分 40
用户昵称 elysian 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-11-03 21:33:58
显示代码纯文本
program factory;
const
fin='factory.in';fout='factory.out';

//f[i]=max{f[j]+a[j+1]*(c[i]-c[j])+b[j+1+k]*s*k  (1<=k<=i-j-1) } (1<=k<=i-1)

var
n,s:longint;
f:array[0..10000] of qword;
a,b:array[0..10000] of int64;
f1,f2:text;

function min2(x,y:int64):int64;
begin
if x<=y then min2:=x else min2:=y;
end;

procedure main;
var
sum,min:int64;
i,j,k:longint;
begin
f[1]:=a[1]*b[1];

for i:=2 to n do
begin
for j:=2 to i do
  begin
  k:=a[j]*b[i]+(i-j)*b[i]*s;
  if (k<f[i])or(f[i]=0) then f[i]:=k;
  end;
end;
min:=0;
for i:=1 to n do
min:=min+f[i];
assign(f2,fout);rewrite(f2);
writeln(f2,min);
close(f2);
End;

procedure init;
var
i,j:longint;
begin
assign(f1,fin);reset(f1);
readln(f1,n,s);
for i:=1 to n do readln(f1,a[i],b[i]);
close(f1);
end;

begin
init;
main;
end.