1070K.md (2169B)
1 Source: https://codeforces.com/problemset/problem/1070/K 2 3 K. Video Posts 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Polycarp took $n$ videos, the duration of the $i$-th video is $a_i$ seconds. The videos are listed in the chronological order, i.e. the $1$-st video is the earliest, the $2$-nd video is the next, ..., the $n$-th video is the last. 22 23 Now Polycarp wants to publish exactly $k$ ($1 \le k \le n$) posts in Instabram. Each video should be a part of a single post. The posts should preserve the chronological order, it means that the first post should contain one or more of the earliest videos, the second post should contain a block (one or more videos) going next and so on. In other words, if the number of videos in the $j$-th post is $s_j$ then: 24 25 * $s_1+s_2+\dots+s_k=n$ ($s_i \gt 0$), 26 * the first post contains the videos: $1, 2, \dots, s_1$; 27 * the second post contains the videos: $s_1+1, s_1+2, \dots, s_1+s_2$; 28 * the third post contains the videos: $s_1+s_2+1, s_1+s_2+2, \dots, s_1+s_2+s_3$; 29 * ... 30 * the $k$-th post contains videos: $n-s_k+1,n-s_k+2,\dots,n$. 31 32 Polycarp is a perfectionist, he wants the total duration of videos in each post to be the same. 33 34 Help Polycarp to find such positive integer values $s_1, s_2, \dots, s_k$ that satisfy all the conditions above. 35 36 Input 37 38 The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$). The next line contains $n$ positive integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where $a_i$ is the duration of the $i$-th video. 39 40 Output 41 42 If solution exists, print "Yes" in the first line. Print $k$ positive integers $s_1, s_2, \dots, s_k$ ($s_1+s_2+\dots+s_k=n$) in the second line. The total duration of videos in each post should be the same. It can be easily proven that the answer is unique (if it exists). 43 44 If there is no solution, print a single line "No". 45 46 Examples 47 48 Input 49 50 ``` 51 6 3 52 3 3 1 4 1 6 53 ``` 54 55 Output 56 57 ``` 58 Yes 59 2 3 1 60 ``` 61 62 Input 63 64 ``` 65 3 3 66 1 1 1 67 ``` 68 69 Output 70 71 ``` 72 Yes 73 1 1 1 74 ``` 75 76 Input 77 78 ``` 79 3 3 80 1 1 2 81 ``` 82 83 Output 84 85 ``` 86 No 87 ``` 88 89 Input 90 91 ``` 92 3 1 93 1 10 100 94 ``` 95 96 Output 97 98 ``` 99 Yes 100 3 101 ```