[코드포스 Practice10] C. Video Posts

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.

Input
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.

Output
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".

---

 

 

문제.. 문제가 너무 길어서 읽는데 힘들었다. 그리고 읽었는데도 이해를 못했다ㅋㅋ

결국에는 예제 보면서 아 이렇게 푸는 거구나 감 잡았음.

 

이것도 푸는 건 간단했다.

동영상 전체 길이를 다 더한 뒤 k개 만큼 나눈다. 다음으로 동영상을 묶어서 이 나눈 길이만큼 되는지 확인하면 된다. 약간 투포인터 느낌 (인데 포인터 하나면 됨)

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    vector<int> v(n);
    vector<int> ans;
    int all_sum = 0;
    for(int i = 0; i<n ; i++){
        scanf("%d", &v[i]);
        all_sum += v[i];
    }
    
    if(all_sum%k != 0){
        printf("No\n");
        return 0;
    }
    
    int count = 0;
    int sum = 0;
    for(int i = 0; i<n ; i++){
        sum += v[i];
        if(sum == all_sum/k){
            ans.push_back(i+1);
            count++;
            sum = 0;
        }
    }
    int before = 0;
    if(k == count){
        printf("Yes\n");
        for(int i = 0; i < ans.size(); i++){
            printf("%d ", ans[i]-before);
            before = ans[i];
        }
    }
    else{
        printf("No\n");
    }
    
    return 0;
}