SRM540 Div1 Easy(250), Div2 Medium(500) ImportantSequence

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;
}};