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?
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.
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;
}
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 ith integer denotes the ith element of L.Constraints
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ min(N*(N+1)/2, 105)
- 1 ≤ Ai ≤ 109
Subtasks
- Subtask 1 (47 pts) : 1 ≤ N ≤ 1000, 1 ≤ K ≤ min{N*(N+1)/2, 105}
- Subtask 2 (53 pts) : 1 ≤ N ≤ 105, 1 ≤ K ≤ min{N*(N+1)/2, 105}
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;
}
No comments:
Post a Comment