Задача "Города"

Как решить задачу на 100 баллов?

Ранним утром субботы, Рауан вышел на серьезную миссию. По трассе M-36, он выехал из Нур-Султана в Алматы, чтобы найти своего друга Хафиза. У Рауана есть мопед с бесконечным бензобаком, но он все еще студент и хочет сэкономить на топливе.
Вдоль двусторонней трассы M-36 расположено 𝑛
населенных пунктов, пронумерованных от 1 до 𝑛. Чтобы проехать между парой соседних населенных пунктов мопед Рауана тратит один псевдо-литр топлива. В 𝑖-м городе Рауан может заправиться по курсу 𝑎𝑖
тенге за псевдо-литр топлива.
Изначально бензобак пуст. Рауан выезжает из города Нур-Султан, имеющий номер 𝑠
, и хочет добраться до города Алматы, имеющий номер 𝑡
. Помогите Рауану определить минимальную сумму денег которую придется потратить на топливо.
Входные данные
В первой строке заданы три целых числа 𝑛, 𝑠, 𝑡 (1≤𝑠, 𝑡≤𝑛≤106).
Во второй строке задано 𝑛
целых чисел 𝑎1, …, 𝑎𝑛, разделенные пробелами (0≤𝑎𝑖≤109).
Выходные данные
Выведите одно целое число — минимальное количество тенге, которое должен потратить Рауан, чтобы добраться до города 𝑡
Система оценки
Данная задача содержит 7
подзадач, в которых выполняются следующие ограничения:

  • Тесты из условия. Оценивается в 0 баллов.
  • 𝑎1=𝑎2=… =𝑎𝑛. Оценивается в 12* баллов.
  • 𝑠=1. Оценивается в 13* баллов.
  • 𝑛≤2000. Оценивается в 20* баллов.
  • 𝑎1≤𝑎2≤… ≤𝑎𝑛. Оценивается в 15* баллов.
  • 𝑛≤105. Оценивается в 25* баллов.
  • Исходные условия задачи. Оценивается в 15
    баллов.

Дейкстра или CHT

Вот разбрр

2 симпатии

а стоп он пропал

Ссылка не работает

Изменил

Что такое СНТ?

convex hull trick

1 симпатия