SRM540 DIV1 easy

easy : ImportantSequence

普通に難しい、intだと通らなかったりするので…

元の数列 {1,2,3,4}と、符号 {+-+} があり、それを計算した結果{3,-1,7}となったが、
元の数列がほしくなった為、{3,-1,7}と{+-+}から元の数列を求めたい。

この場合{1,2,3,4}と{2,1,2,5}の2通りがあるため
答えは2通りとなる。

a[0]が決まれば、自動的にa[3]が決まるので、a[3]の範囲が求まればいい。
1 <= a[0]なので、1 <= a[1] <= 2, 2 <= a[2] <= 3, 4 <= a[3] <= 5
となること利用して、答えを出す。

#ifdef TEST_CODE
#define typeof(X) std::identity<decltype(X)>::type //C++0x
#else
#define typeof(X) __typeof__(X) // for gcc
#endif

#define sz(a)  int((a).size())
#define FOREACH(it, c) for (typeof((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define FOR(i,n) for(int i = 0; i < (n); i++)

using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class ImportantSequence {
public:
  int getCount(vector <int> B, string operators) {
	  ll mn = 1,mx = LLONG_MAX;
	FOR(i,sz(B)){
		ll nmn,nmx;
		if(operators[i] == '+'){
			if(mn > B[i]) return 0;
			nmn = max<ll>(B[i] - mx,1);
			nmx = B[i] - mn;
		} else {
			if(mx <= B[i]) return 0;
			nmn = max<ll>(1, mn- B[i]);
			nmx = (mx == LLONG_MAX) ? LLONG_MAX : mx - B[i];
		}
		mn = nmn; mx = nmx;
	}
	if(mx == LLONG_MAX) return -1;
	return (int)(mx - mn) + 1;
  }

};