시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 163 | 94 | 87 | 59.184% |
The volcanic island of Fleeland has never had a proper electric net, but finally the administration of the island have agreed to build the island's power plants and network.
On the island's coast are its $n$ cities. The administration has surveyed the cities and proposed $m$ of them as possible locations for a power plant, with the $i$th proposal stating that the company can build a plant in city $c_i$ for cost $a_i$.
These power plants are very modern and a single plant could power the whole island, but the volcano makes building power lines across the island a dangerous affair. For $1 \leq i < n$, the company can build power lines between cities $i$ and $i+1$ for a cost of $b_i$, and between cities $n$ and $1$ for a cost of $b_n$. A city will receive power if it contains a power plant or is connected to a city with a power plant via power lines.
What is the cheapest way to power all the cities on the island?
The values of $c_{1,\ldots,n}$ are unique and given in strictly increasing order.
Output the minimal cost of powering all cities on the island.
3 2 1 100 2 200 150 300 150
400
3 2 1 100 2 200 300 300 150
450
ICPC > Regionals > Europe > Northwestern European Regional Contest > The UK & Ireland Programming Contest > UKIEPC 2020 G번
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2020 G번