My AC code is those:
Program RailwayTickets;
Const MaxN = 10000;
Var L,C : Array [1 .. 3] Of LongInt;
Stops : Array [1 .. 3,1 .. MaxN] Of LongInt;
Costs,D : Array [1 .. MaxN] Of LongInt;
Start,Finish,I,N : Word;
J : Byte;
S,Min,T : LongInt;
BEGIN {
Assign(Input,'1031.in'); Reset(Input);
Assign(Output,'1031.out'); ReWrite(Output);}
Read(L[1],L[2],L[3],C[1],C[2],C[3],N,Start,Finish);
D[1] := 0;
For I := 2 To N Do
Read(D[I]);
If Start > Finish
Then begin
I := Start;
Start := Finish;
Finish := I;
end;
Stops[1,Start] := Start;
Stops[2,Start] := Start;
Stops[3,Start] := Start;
For I := Start + 1 To Finish Do
For J := 1 To 3 Do
begin
S := Stops[J,I - 1];
While D[I] - D[S] > L[J] Do
Inc(S);
Stops[J,I] := S;
end;
Costs[Start] := 0;
For I := Start + 1 To Finish Do
begin
Min := MaxLongInt;
For J := 1 To 3 Do
If Stops[J,I] <> I
Then begin
T := Costs[Stops[J,I]] + C[J];
If T < Min
Then Min := T;
end;
Costs[I] := Min;
end;
WriteLn(Costs[Finish]);
END.
I think that it has complexity O(3 * N). Am I wrong?
I use Turbo Pascal 7.0, because shell of Free Pascal is
unstable on my computer. That is the why when I post my solution
first time I forgot to change MaxN to 10000 and got TLE :).
P.S. Sorry for bad English.