P9468 [EGOI 2023] Candy / Candy

Day 2 Problem B. Translated from [EGOI2023 candy](https://egoi23.se/assets/tasks/day2/candy.pdf). [](https://creativecommons.org/licenses/by-sa/3.0/)

In the city of Ikaagu, it is said that there is a palace whose wealth is beyond imagination. Inside it, along a corridor, there are $N$ boxes of candy from all over the world. Any traveler passing by can take as much candy as they want, as long as they pay gold equal to the weight of the candy. The boxes are numbered from left to right from $0$ to $N-1$. In box $i$, there are $a_i$ units of candy remaining, where $a_i$ is a non-negative integer. As the guardian of the palace, you need to move these boxes so that boxes with lots of candy are closer to the entrance. You are given the array $a_0,a_1,\cdots,a_{N-1}$, and integers $F$ and $T$. In one operation, you are allowed to swap any two **adjacent** elements in $a_0,a_1,\cdots,a_{N-1}$. What is the minimum number of operations needed to make the sum of the first $F$ elements of the array at least $T$?

The first line contains three integers $N,F,T$. The second line contains $N$ integers $a_0,a_1,\cdots,a_{N-1}$.

If it is impossible to achieve the goal, output `NO`. Otherwise, output one integer, the minimum number of operations.

**Sample $1$ Explanation** In sample $1$, the sum of the first two elements must be at least $27$. This can be achieved with one adjacent swap: swap $4$ and $20$. After the swap, the array becomes `10 20 4 6 3 3`, and the sum of the first two elements is $10+20=30\ge 27$. --- **Sample $2$ Explanation** In sample $2$, the $0$ must be moved all the way to the end of the array; this requires $3$ swaps. --- **Sample $3$ Explanation** In sample $3$, it is impossible to make the sum of the first two elements at least $100$; the best we can do is $60+30=90$. --- **Constraints** For all testdata, $1\le N\le 100$, $1\le F\le N$, $0\le T\le 10^{11}$, $0\le a_i\le 10^9$. - Subtask 1 ($6$ points): $N\le 2$, $a_i\le 100$, $T\le 10^9$. - Subtask 2 ($19$ points): $a_i\le 1$. - Subtask 3 ($16$ points): $N\le 20$. - Subtask 4 ($30$ points): $a_i\le 100$. - Subtask 5 ($29$ points): no additional constraints. --- **Hint** The answer may not fit in a 32-bit integer. If you use C++, watch out for possible overflow. Translated by ChatGPT 5