ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1031. Железнодорожные билеты

n*log(n)
Послано Sergeyev Alexander 9 сен 2003 18:56
var
  s:array[1..10000] of longint;
  n:integer;
function search(v,st:longint):integer;
var cyc1,cyc2,tm:integer;
begin
  cyc1:=st-1;
  cyc2:=n;
  while cyc1<cyc2-1 do
  begin
    tm:=(cyc1+cyc2)div 2;
    if s[tm]=v then break;
    if s[tm+1]=v then break;
    if s[tm]>v then cyc2:=tm-1 else cyc1:=tm;
  end;
  tm:=(cyc1+cyc2)div 2;
  if s[tm]<=v then search:=tm;
  if s[tm+1]<=v then search:=tm+1;

end;
var
  s1,s2:longint;
  m:array[1..10000] of longint;
  cyc1,cyc2,tm1:longint;
  p,l,c:array[1..3] of longint;
begin
  readln(l[1],l[2],l[3],c[1],c[2],c[3]);
  readln(n);
  readln(s1,s2);
  if s1>s2 then begin cyc2:=s1;s1:=s2;s2:=cyc2; end;
  for cyc1:= 2 to n do
    readln(s[cyc1]);

  for cyc1:= s1 to s2 do
   if (m[cyc1]<>0)or(cyc1=s1) then
   begin
     for cyc2:=1 to 3 do
       begin
         tm1:=search(s[cyc1]+l[cyc2],cyc1-1);
         if (tm1<>cyc1)and((m[tm1]>m[cyc1]+c[cyc2])or(m[tm1]=0)) then
         m[tm1]:=m[cyc1]+c[cyc2];
         if (tm1>s2)and(m[s2]=0) then m[s2]:=m[tm1];
      end;
   end;
  writeln(m[s2]);
end.