| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 74 | 19 | 15 | 22.388% |
Farmer Gumbauskas is growing potatoes. He planted potatoes in one long furrow and placed bags with fertilisers next to the furrow.
Assume that the furrow consists of $N$ segments of the same length. The segments are numbered from 1ドル$ to $N$ from left to right. In segment $i$ there are $a_i$ fertilisers and were planted $b_i$ potatoes. One fertiliser unit is required to fertilise one planted potato. There is enough fertiliser for all the potatoes, i.e. $a_1 + \cdots + a_N ≥ b_1 + \cdots + b_N$.
However, it costs to transfer fertiliser from one segment to another. To transfer one unit of fertiliser from segment $i$ to segment $j$ costs $|i - j|$.
Find the cheapest way to fertilise all the potatoes.
The length of the furrow $N$ is given in the first line.
Each of the remaining $N$ lines contain two integers $a_i$ and $b_i$ – the amount of fertiliser unit and the amount of potatoes planted in segment $i$. The segments are given in the increasing order of $i$.
Output the smallest possible cost of fertilising all the planted potatoes.
Further the following notation will be used: $A = a_1 + \cdots + a_N$ and $B = b_1 + \cdots + b_N$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 24 | The same amount of fertiliser and potatoes: $A = B$ |
| 2 | 10 | $A = B$ or $A = B + 1$ |
| 3 | 20 | $N ≤ 3000$ and $A, B ≤ 30,000円$ |
| 4 | 10 | $N ≤ 3000$ |
| 5 | 36 | No additional constraints |
6 1 2 0 0 2 0 0 0 0 0 0 1
5
The cheapest way to fertilise all the potatoes (fertiliser is indicated above the horizontal line, potatoes are below the line):
Adding the distances we get: 0ドル + 2 + 3 = 5$.
7 2 0 2 0 2 0 0 5 2 0 2 0 2 0
6
The fertiliser for four potatoes is transferred from neighbouring segments, while for the remaining potato it is delivered from further located segment.
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2018/2019 > Final Round 1번