***Maximum K Sums ( find all possible sub array sum and print firs k maximum sum )

Maximum K Sums

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:

--------------------------------------EDITORIAL-----------------------------------------------------------

PREREQUISITES:

Sorting, Greedy, Data Structure, Implementation.

PROBLEM STATEMENT:

Given an array A$A$ containing N$N$ positive integers and an integer K$K$. We are asked to report the largest K$K$ values from the list of sums of all possible subarrays of array A$A$.

EXPLANATION:

Subtask 1

Listing sums of all the possible subarrays of A$A$ and finding the largest K$K$ values will be enough to pass this subtask.

C++ Code

#define ll long long
void solve(int N, int K, int *arr) {
    vector<ll> sum;
    for(int i=1;i<=n;i++) {
        long long int s = 0;
        for(int j=i;j<=n;j++) {
            s += arr[j];
            sum.push_back(s);
        }
    }
    sort(sum.rbegin(), sum.rend());
    for(int i=0; i<=K-1; i++) cout << sum[i] << " ";
    cout << "\n";
}

Time Complexity

O((N×(N+1)2))×logN×(N+1)2)$O((\frac{N\times (N+1)}{2}))\times \log \frac{N\times (N+1)}{2})$

Complete Code Link

Note

Although the above solution will get passed on first subtask but we can have slight better complexity by maintaining a priority queue for the first K$K$ elements instead of sorting all the sums.

Complete Code Link

Subtask 2

It is easy to see that the above solution will time out for this subtask.

Then, how to approach it ?

It can be noticed that the largest and first value will always be sum of all the elements as it is given that all elements are positive integers. It means the sum is corresponding to the subarray [1toN]$[1toN]$ inclusively. Now, we have taken up the range 1...N$\mathrm{1...}N$ and we can see that the next possible largest sum will be the maximum of sum of range 2...N$\mathrm{2...}N$ and range 1...N−1$\mathrm{1...}N-1$. Let us assume that the second largest is obtained from the range 1...N−1$\mathrm{1...}N-1$. Then, the third largest sum will be maximum of sum of range 2...N$\mathrm{2...}N$ ( previous range left ), range 2...N−1$\mathrm{2...}N-1$ and range 1...N−2$\mathrm{1...}N-2$ ( new ranges ). The above procedure can be run K$K$ times to find the largest K$K$ values.

How to implement above idea ?

Let us maintain a priority queue S$S$ ( set can also be used in C++ ). So, whenever we are taking the sum of a range say [L to R] from S, we can simply insert 2 new values to S$S$ i.e sum of range [L+1toR]$[L+1toR]$ and [LtoR−1]$[LtoR-1]$ if L!=R$L!=R$. Note that along with sum of range we are also maintaining the indices i.e L$L$ and R$R$ denoting that range in our priority queue.

C++ Code

#define ll long long
void solve(int N, int K, int *arr) {
    set<pair<ll,pair<int,int>> S;
    long long int prefix_sum[N+1];
    for(int i=1;i<=n;i++) {
        prefix_sum[i] = prefix_sum[i-1] + arr[i];
    }

    S.insert({prefix_sum[N], {1, N}});
    while( K -- && !S.empty() ) {
        pair<ll,pair<int,int>> top = *S.begin();
        S.erase( top );
        long long int sum;
        int L, R;
        sum = top.first;
        L = top.second.first;
        R = top.second.second;
        cout << sum <<" ";
        if( L != R ) {
            S.insert({sum-arr[L], {L+1, R}});
            S.insert({sum-arr[R], {L, R-1}});
        }
    }   
} 

TIME COMPLEXITY:

O(K×logK)$O(K\times \log K)$

-------------------------------CODE--------------------------------------------------------

// I USED SET INSTEAD OF PQ

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

set<pair<pair<lli,int>,int> > s;

map<pair<int,int> ,int> ma;

lli arr[1000000];

int main()

 {

   int n,m;

   cin>>n>>m;

   lli sum=0;

   for(int i=0;i<n;i++)

    {

      cin>>arr[i];

      sum+=arr[i];

   }

   s.insert({{sum,0},n-1});

for(int i=0;i<m;i++)

 {

    while(1)

     {

      set<pair<pair<lli,int>,int> > :: reverse_iterator ite;

      ite=s.rbegin();

      pair<pair<lli,int>,int> pp;

      lli sum=ite->first.first;

      int l=ite->first.second;

      int  r=ite->second;

      s.erase({{sum,l},r});

     

      if(ma[{l,r}]==0)

       {

        ma[{l,r}]=1;

         cout<<sum<<" ";

         s.insert({{sum-arr[l],l+1},r});

         s.insert({{sum-arr[r],l},r-1});

         break;

  }

      

    

}

 }

   

 }