In this HackerEarth To Take or Not To Take problem solution Pandey needs your help. As you know, he is on the quest to save the princess. After traveling for a number of days, he has finally reached the palace, but one last battle remains to be fought. However, he has only one unit of energy left in him. To win the battle, he needs all the energy he can get. So he is searching for the Wizard of GJ.

GJ agrees to help him if he is willing to play his game. GJ will give him B balloons, one at a time. For each balloon, he will ask Pandey if he wants to take the balloon. If Pandey accepts, his energy level will be changed according to the value and type of the balloon. Otherwise, the balloon is lost forever.

GJ is hoping to enjoy seeing Pandey regret his choices after every move because Pandey will only know the current balloon offered to him and will have no knowledge of the following ones. However, unknown to GJ, Pandey's brother Vajpayee had been working undercover as GJ's apprentice and knew in advance the values on each of the balloons and also the order in which he would show them to Pandey. So, Pandey knows all the details, and now he needs you to help him select the balloons so that he can maximize his energy.


HackerEarth To Take or Not To Take problem solution


HackerEarth To Take or Not To Take problem solution.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll f(ll a, char type, ll x) {
  if(type == 'N') return -a;
  else if(type == '+') return a+x;
  else if(type == '-') return a-x;
  else if(type == '*') return a*x;
  else if(type == '/') return a/x;
  else assert(false);
}

void te() {
  int n;
  scanf("%d", &n);
  ll mi = 1, ma = 1;
  for(int i = 0; i < n; ++i) {
    char sl[3];
    scanf("%s", sl);
    int x;
    if(sl[0] != 'N') scanf("%d", &x);
    vector<ll> maybe;
    maybe.push_back(mi);
    maybe.push_back(ma);
    maybe.push_back(f(mi, sl[0], x));
    maybe.push_back(f(ma, sl[0], x));
    sort(maybe.begin(), maybe.end());
    mi = maybe[0];
    ma = maybe.back();
    ll M = 1000 * 1000 * 1000;
    M *= M;
    assert(max(abs(mi), abs(ma)) <= M);
  }
  printf("%lld\n", ma);
}

int main() {
  int z;
  scanf("%d", &z);
  while(z--) te();
  return 0;
}