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.

Download