CF1070K.Video Posts

普及-

通过率:0%

时间限制:3.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Polycarp took nn videos, the duration of the ii-th video is aia_i seconds. The videos are listed in the chronological order, i.e. the 11-st video is the earliest, the 22-nd video is the next, ..., the nn-th video is the last.

Now Polycarp wants to publish exactly kk (1≤k≤n1 \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 jj-th post is sjs_j then:

  • s1+s2+⋯+sk=ns_1+s_2+\dots+s_k=n (si>0s_i \gt 0),
  • the first post contains the videos: 1,2,…,s11, 2, \dots, s_1;
  • the second post contains the videos: s1+1,s1+2,…,s1+s2s_1+1, s_1+2, \dots, s_1+s_2;
  • the third post contains the videos: s1+s2+1,s1+s2+2,…,s1+s2+s3s_1+s_2+1, s_1+s_2+2, \dots, s_1+s_2+s_3;
  • ...
  • the kk-th post contains videos: n−sk+1,n−sk+2,…,nn-s_k+1,n-s_k+2,\dots,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,…,sks_1, s_2, \dots, s_k that satisfy all the conditions above.

波利卡普拍摄了 nn 段视频,其中第 ii 段视频的时长为 aia_i 秒。这些视频按时间顺序排列,即第 11 段视频最早,第 22 段视频次之,……,第 nn 段视频最晚。

现在波利卡普希望在 Instabram 上恰好发布 kk(1≤k≤n1 \le k \le n)个帖子。每段视频必须且仅属于一个帖子。帖子需保持原始的时间顺序,即第一个帖子应包含一段(或若干段)最早的视频,第二个帖子应包含紧随其后的一段(或若干段)视频,依此类推。换言之,若第 jj 个帖子包含 sjs_j 段视频,则需满足:

  • s1+s2+⋯+sk=ns_1+s_2+\dots+s_k=n(其中每个 si>0s_i > 0);
  • 第一个帖子包含视频编号:1,2,…,s11, 2, \dots, s_1;
  • 第二个帖子包含视频编号:s1+1,s1+2,…,s1+s2s_1+1, s_1+2, \dots, s_1+s_2;
  • 第三个帖子包含视频编号:s1+s2+1,s1+s2+2,…,s1+s2+s3s_1+s_2+1, s_1+s_2+2, \dots, s_1+s_2+s_3;
  • ……
  • 第 kk 个帖子包含视频编号:n−sk+1,n−sk+2,…,nn-s_k+1, n-s_k+2, \dots, n。

波利卡普是个完美主义者,他希望每个帖子中所有视频的总时长完全相等。

请帮助波利卡普找出满足上述所有条件的正整数 s1,s2,…,sks_1, s_2, \dots, s_k。

输入格式

The first line contains two integers nn and kk (1≤k≤n≤1051 \le k \le n \le 10^5). The next line contains nn positive integer numbers a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤1041 \le a_i \le 10^4), where aia_i is the duration of the ii-th video.

第一行包含两个整数 nn 和 kk(1≤k≤n≤1051 \le k \le n \le 10^5)。下一行包含 nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n(1≤ai≤1041 \le a_i \le 10^4),其中 aia_i 表示第 ii 个视频的时长。

输出格式

If solution exists, print "Yes" in the first line. Print kk positive integers s1,s2,…,sks_1, s_2, \dots, s_k (s1+s2+⋯+sk=ns_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).

If there is no solution, print a single line "No".

如果存在解,在第一行输出“Yes”。在第二行输出 kk 个正整数 s1,s2,…,sks_1, s_2, \dots, s_k(满足 s1+s2+⋯+sk=ns_1+s_2+\dots+s_k=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测评打分。不知道怎么写?

首页