stacks and queues

[1vf9z8AR]

Problem-
You are given a stack of N integers such that the first element represents the top of the stack and the last element represents the bottom of the stack. You need to pop at least one element from the stack. At any one moment, you can convert stack into a queue. The bottom of the stack represents the front of the queue. You cannot convert the queue back into a stack. Your task is to remove exactly K elements such that the sum of the K removed elements is maximised.

Input format :

The first line consists of two space-separated integers N and K.
The second line consists of N space-separated integers denoting the elements of the stack.
Output format :

Print the maximum possible sum of the K removed elements

SAMPLE INPUT
10 5
10 9 1 2 3 4 5 6 7 8
SAMPLE OUTPUT
40
Explanation
Pop two elements from the stack. i.e {10,9}

Then convert the stack into queue and remove first three elements from the queue. i.e {8,7,6}.

The maximum possible sum is 10+9+8+7+6 = 40

  #include<iostream>
using namespace std;
long long int ans=0,currentsum;
int n,k,arr[100000];
int answer(int x)
{
    int ilimit=x-1;
    int jlimit=n-k+x+1;
    currentsum=0;
    for(int i=0;i<=ilimit;i++)
        currentsum+=arr[i];
    for(int j=n;j>=jlimit;j--)
        currentsum+=arr[j];
    if(currentsum>ans)
        ans=currentsum;
    return 0;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    n--;
    for(int x=1;x<=k;x++)
        answer(x);
    cout<<ans;
    return 0;
}

Issue-
I am getting time limit exceeded for some cases

My logic-
Find answer by going through all possible arrangements.
like for n=10 k=5
i=0 1 2 3 4
i=0 1 2 3 4 j=9
i = 0 1 2 3 j = 9 8
and so on

[mbozzi]

Just store the partial sums so you don't have to compute them k times.

// Problem: You are given a stack of N integers such that the first element
//   represents the top of the stack and the last element represents the bottom
//   of the stack.  You need to pop at least one element from the stack.  At any
//   one moment, you can convert stack into a queue.  The bottom of the stack
//   represents the front of the queue.  You cannot convert the queue back into
//   a stack.  Your task is to remove exactly K elements such that the sum of
//   the K removed elements is maximised.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

int main() {
  int n = 0, k = 0;

  if (!(std::cin >> n >> k))
    return 1;

  if (n < k || k < 1)
    return 2;

  // lsums and rsums hold the forward (left) and backward (right) partial-sums
  // of the input data-set.  Prepend 0 so that *sums[i] is the sum of the first
  // i elements.
  std::vector<int> lsums{0}, rsums{0};

  { // fill lsums, rsums:
    using std::begin, std::end, std::rbegin, std::rend;

    std::vector<int> data;
    std::copy_n(std::istream_iterator<int>{std::cin}, n,
                std::back_inserter(data));

    std::partial_sum(begin(data), end(data), std::back_inserter(lsums));
    std::partial_sum(rbegin(data), rend(data), std::back_inserter(rsums));
  }

  if (!(std::cin))
    return 1;

  int max_sum = 0;
  for (int a = 1; a <= k; ++a)
    if (int const sum = lsums[a] + rsums[k - a]; max_sum < sum)
      max_sum = sum;

  std::cout << max_sum << '\n';
}

http://coliru.stacked-crooked.com/a/54c57f47d7817c97

[salem c]

> My logic-
> Find answer by going through all possible arrangements.
Which isn't what the problem stated.

> Issue-
> I am getting time limit exceeded for some cases
Work smarter, not harder.

The assignment calls for stacks and queues - neither of which you use.

Put down the mouse, step away from the keyboard and grab a pencil and some paper.

Actually think about the problem, discover what 'stack and queue' might be trying to tell you about the problem and come up with a smarter answer.

[1vf9z8AR]

@salem c

are you saying that I can find the answer without checking each combination?

[1vf9z8AR]

@mbozzi

Your method was so fast. Go accepted by a lot of time left.

[salem c]

> are you saying that I can find the answer without checking each combination?
Apparently, but then mbozzi came along and you skipped the step about thinking for yourself.

You just went for the "Your method was so fast. Go accepted by a lot of time left." and seem to have learnt nothing.

So now you're back with yet another problem.
http://www.cplusplus.com/forum/beginner/247883/

Is this your work-flow?
- read question
- write first thing that comes into your head
- upload it, it doesn't work
- post code on a forum
- get a better answer

I hope you're not planning to get a paid career based on your "achievement" to date.

[mbozzi]

@suyashing234 was very close to a solution. All that he needed to do was save some intermediate work (the for-loops in answer()).

In any event, the program above has an error: lsums, rsums should be a vector of long long int. Otherwise there is potential for signed integer overflow. I guess it was good enough for the input data, though.

[dutch]

@mbozzi
You should always start a "competitive programming" solution in C++ with the following. It can really make a difference. It makes your program more than twice as fast for me.

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

[kbw]

You do realize that std::cin and std::cout are tied for a reason right?

[dutch]

You do realize that std::cin and std::cout are tied for a reason right?

You do realize that that reason does not apply to competitive programming inputs, right?

[1vf9z8AR]

@salem c
actually, I did learn a lot. What I was doing was correct but coded in a slower manner.

mbozzi helped me make it faster.

not learning would be posting completely wrong code and getting answers.