PTRANG - Phân Trang
Tác giả: ll931110
Ngôn ngữ: Pascal
Program PTRANG;
Const
input = '';
output = '';
Var
n,l: longint;
a,s,F: array[1..6000] of longint;
Procedure init;
Var
fi: text;
i: longint;
Begin
Assign(fi, input);
Reset(fi);
Readln(fi, n, l);
For i:= 1 to n do readln(fi, a[i]);
Close(fi);
End;
Procedure sum;
Var
i: longint;
Begin
s[1]:= a[1];
For i:= 2 to n do s[i]:= s[i - 1] + a[i];
End;
Function max(x,y: longint): longint;
Begin
If x < y then max:= y else max:= x;
End;
Procedure optimize;
Var
i,k: longint;
Begin
F[1]:= l - s[1];
For i:= 2 to n do
Begin
F[i]:= l - s[i];
If F[i] < 0 then F[i]:= 1000000000;
For k:= 1 to i - 1 do
If (F[i] > max(F[k], l - (s[i] - s[k]))) and (l - (s[i] - s[k]) >= 0)
then F[i]:= max(F[k], l - (s[i] - s[k]));
End;
End;
Procedure solve;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
Writeln(fo, F[n]);
Close(fo);
End;
Begin
init;
sum;
optimize;
solve;
End.