406117: GYM102268 J Jealous Split

Memory Limit:0 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Jealous Splittime limit per test2 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard output

You have an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$.

You need to split it into $$$k$$$ non-empty subsegments: $$$[1; b_1], [b_1 + 1; b_2], \ldots, [b_{k - 1} + 1; n]$$$.

Let us denote the sum on $$$i$$$-th segment as $$$s_i$$$ and the maximum on $$$i$$$-th segment as $$$m_i$$$. Your goal is to make $$$|s_i - s_{i+1}| \leq \max({m_i, m_{i+1}})$$$ for each $$$1 \leq i \leq k - 1$$$.

Input

The first line of the input contains two integers $$$n$$$ and $$$k$$$: the size of the array and the required number of segments ($$$3 \leq k \leq n \leq 100\,000$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$: the given array ($$$0 \leq a_i \leq 50\,000$$$).

Output

If splitting is possible, print "Yes" on the first line, and then print $$$k - 1$$$ space-separated integers $$$b_1, b_2, \ldots, b_{k - 1}$$$ on the second line. The integers must satisfy $$$1 \leq b_1 < b_2 < \ldots < b_{k - 1} < n$$$. Additionally, the inequalities $$$|s_i - s_{i+1}| \leq \max({m_i, m_{i+1}})$$$ must hold for each $$$1 \leq i \leq k - 1$$$. If there are several possible solutions, print any one of them.

If splitting is impossible, print "No" on a single line.

ExampleInput
5 3
17 18 17 30 35
Output
Yes
2 4

Source/Category

加入题单

上一题 下一题 算法标签: