| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 15 | 3 | 3 | 23.077% |
You live in an archipelago consisting of $N$ islands (numbered from $1$ to $N$) laid out in a single line. Island $i$ is adjacent to island $i+ 1$, for $1 ≤ i < N$. Between adjacent islands $i$ and $i+ 1$, there is a pair of one-directional underwater tunnels: one that allows you to walk from island $i$ to island $i+1$ and one for the opposite direction. Each tunnel can only be traversed at most once.
You also have a dragon with you. It has a stamina represented by a non-negative integer. The stamina is required for the dragon to perform its abilities: swim and fly. Initially, its stamina is $0$.
Your dragon’s stamina can be increased as follows. There is a magical shrine on each island $i$ that will immediately increase your dragon’s stamina by $P_i$ (regardless the position of the dragon) when you visit island $i$ for the first time. This event takes no time.
When you are on an island, there are $3$ moves that you can perform.
Note that both swimming and flying do not use tunnels.
Your dragon and you are currently on island $1$. Your mission is to go to island $N$ with your dragon. Determine the minimum possible time to complete your mission.
The first line consists of five integers $N$ $D$ $T_s$ $T_f$ $T_w$ ($2 ≤ N ≤ 200\, 000$; $1 ≤ D, T_s, T_f , T_w ≤ 200\, 000$).
The second line consists of $N$ integers $P_i$ ($1 ≤ P_i ≤ 200\, 000$).
Output an integer in a single line representing the minimum possible time to go to island $N$ with your dragon.
5 4 2 9 1 1 2 4 2 1
28
The following sequence of events will complete your mission in the minimum time.
5 4 2 1 1 1 2 4 2 1
4
Repeat the following process for $1 ≤ i < 5$: The shrine on island $i$ increases your dragon’s stamina, then use the stamina to fly with your dragon to island $i + 1$.
3 4 2 10 1 3 1 2
16