SRM540 Div1 Easy(250), Div2 Medium(500) ImportantSequence
最左の数字を決めれば、全ての数字が定まる。数字1個ずつ処理すると時間が足りないので、それぞれの数字が取り得る範囲で計算する。
#include <string> #include <vector> using namespace std; class ImportantSequence{public: int getCount( vector <int> B, string operators ) { int N = (int)B.size()+1; long long mn = 1; long long mx = 1LL<<60; for ( int i=0; i<N-1; i++ ) { long long pmn = mn; long long pmx = mx; if ( operators[i]=='-' ) { mn = pmn-B[i]; mx = pmx-B[i]; } else { mx = B[i]-pmn; mn = B[i]-pmx; } mx = max( 0LL, mx ); mn = max( 1LL, mn ); } return mx-mn+1 < (1LL<<32) ? mx-mn+1 : -1; }};