Maximum K Sums (First Approach)

Problem Statement
Chef likes arrays a lot. Today, he found an array A consisting of N positive integers.
Let L denote the sorted (in non-increasing order) list of size N*(N+1)/2 containing the sums of all possible contiguous subarrays of A. Chef is interested in finding the first K elements from the list L. Can you help him in accomplishing this task?

Input

There is only a single test case per input file.
The first line of input contains two space separated integer numbers N and K denoting the size of the array and the number of the maximal sums you need to find.
The following line contains N space separated integer numbers denoting the array A.

Output

Output K space separated integers where the i^th integer denotes the i^th element of L.

Constraints

• 1 ≤ N ≤ 10⁵


• 1 ≤ K ≤ min(N*(N+1)/2, 10⁵)


• 1 ≤ A_i ≤ 10⁹

Subtasks

• Subtask 1 (47 pts) : 1 ≤ N ≤ 1000, 1 ≤ K ≤ min{N*(N+1)/2, 10⁵}
• Subtask 2 (53 pts) : 1 ≤ N ≤ 10⁵, 1 ≤ K ≤ min{N*(N+1)/2, 10⁵}

Example

Input 1
3 4
1 3 4

Output 1
8 7 4 4

Input 2
3 3
10 2 7

Output 2
19 12 10

Explanation

Test 1:


The first 4 elements of it are [8, 7, 4, 4].


Problem link :  KSUM

The idea : Here I will be discussing the brute force approach to solve this problem . This will ensure that you will partially solve the problem . The full solving approach will be discussed in the next post.
The idea is very simple . Generate all sums by simply taking the starting point  'i' as fixed and iterating 'j' right till the end. Now push this in to a vector. Sort it in reverse end by this sort(r.begin(),r.end()) .
Now print these elements.

The Code:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    vector<long long int> v;
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)
    {
        int number;
        scanf("%d",&number);
        v.push_back(number);
    }
    vector<long long int> sumArr;
    for(int i=0;i<n;i++)
    {
        long long int sum=0;
        for(int j=i;j<n;j++)
        {
            sum+=v[j];
            sumArr.push_back(sum);
           
        }
    }
    sort(sumArr.rbegin(),sumArr.rend());
    for(int i=0;i<k;i++)
    {
        cout<<sumArr[i]<<" ";
       
    }
    cout<<endl;
   
   
    return 0;
}