QBTICKET - Mua vé tàu hoả

Tác giả: ladpro98

Ngôn ngữ: Pascal

program qbticket;
uses    math;
const   fi='';
        maxN=100005;
        oo=trunc(1e18);
var     a,f:array[1..maxN] of int64;
        n,st,fin,l1,l2,l3,c1,c2,c3:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,l1,l2,l3,c1,c2,c3);
        readln(inp,n);
        readln(inp,st,fin);
        a[1]:=0;
        for i:=2 to n do
        readln(inp,a[i]);
        close(inp);

end;

function find(r:longint;key:int64):longint;
var     l,m,k:longint;
begin
        l:=st;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if a[m]>=key then
                begin
                        k:=m;
                        r:=m-1;
                end
                else l:=m+1;
        end;
        exit(k);
end;

procedure dp;
var     i,x,y,z:longint;
begin
        f[st]:=0;
        for i:=st+1 to fin do
        begin
                x:=find(i,a[i]-l1);
                y:=find(i,a[i]-l2);
                z:=find(i,a[i]-l3);
                f[i]:=oo;
                if x<>i then f[i]:=min(f[i],f[x]+c1);
                if y<>i then f[i]:=min(f[i],f[y]+c2);
                if z<>i then f[i]:=min(f[i],f[z]+c3);
        end;
end;

begin
        input;
        dp;
        write(f[fin]);
end.

Download