CF1070K.Video Posts
普及-
通过率:0%
时间限制:3.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Polycarp took n videos, the duration of the i-th video is ai 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.
Now Polycarp wants to publish exactly k (1≤k≤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 sj then:
- s1+s2+⋯+sk=n (si>0),
- the first post contains the videos: 1,2,…,s1;
- the second post contains the videos: s1+1,s1+2,…,s1+s2;
- the third post contains the videos: s1+s2+1,s1+s2+2,…,s1+s2+s3;
- ...
- the k-th post contains videos: n−sk+1,n−sk+2,…,n.
Polycarp is a perfectionist, he wants the total duration of videos in each post to be the same.
Help Polycarp to find such positive integer values s1,s2,…,sk that satisfy all the conditions above.
波利卡普拍摄了 n 段视频,其中第 i 段视频的时长为 ai 秒。这些视频按时间顺序排列,即第 1 段视频最早,第 2 段视频次之,……,第 n 段视频最晚。
现在波利卡普希望在 Instabram 上恰好发布 k(1≤k≤n)个帖子。每段视频必须且仅属于一个帖子。帖子需保持原始的时间顺序,即第一个帖子应包含一段(或若干段)最早的视频,第二个帖子应包含紧随其后的一段(或若干段)视频,依此类推。换言之,若第 j 个帖子包含 sj 段视频,则需满足:
- s1+s2+⋯+sk=n(其中每个 si>0);
- 第一个帖子包含视频编号:1,2,…,s1;
- 第二个帖子包含视频编号:s1+1,s1+2,…,s1+s2;
- 第三个帖子包含视频编号:s1+s2+1,s1+s2+2,…,s1+s2+s3;
- ……
- 第 k 个帖子包含视频编号:n−sk+1,n−sk+2,…,n。
波利卡普是个完美主义者,他希望每个帖子中所有视频的总时长完全相等。
请帮助波利卡普找出满足上述所有条件的正整数 s1,s2,…,sk。
输入格式
The first line contains two integers n and k (1≤k≤n≤105). The next line contains n positive integer numbers a1,a2,…,an (1≤ai≤104), where ai is the duration of the i-th video.
第一行包含两个整数 n 和 k(1≤k≤n≤105)。下一行包含 n 个正整数 a1,a2,…,an(1≤ai≤104),其中 ai 表示第 i 个视频的时长。
输出格式
If solution exists, print "Yes" in the first line. Print k positive integers s1,s2,…,sk (s1+s2+⋯+sk=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).
If there is no solution, print a single line "No".
如果存在解,在第一行输出“Yes”。在第二行输出 k 个正整数 s1,s2,…,sk(满足 s1+s2+⋯+sk=n)。每条帖子中视频的总时长应相等。可以轻松证明:若解存在,则该解唯一。
若无解,仅输出一行“No”。
输入输出样例
输入#1
6 3 3 3 1 4 1 6
输出#1
Yes 2 3 1
输入#2
3 3 1 1 1
输出#2
Yes 1 1 1
输入#3
3 3 1 1 2
输出#3
No
输入#4
3 1 1 10 100
输出#4
Yes 3
输入解题思路,AI测评打分。不知道怎么写?