Submission #1688585

---

Source Code Expand

#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define I(n) scanf("%d", &(n))
#include <bits/stdc++.h>
using namespace std;
int itwo;
long long dp[2][100021],m,slen;
string s;

int main(){
    cin >> s;
    slen = s.length();
    dp[0][50010] = (int64_t)1<<40;
    itwo = 1;
    REP(i,slen){
        itwo ^= 1;
        if (s[i] == 'M'){
            FOR(k,50010-m,50010+m+1){
                if ((k-m)%2){
                    dp[itwo^1][k] = max(dp[itwo][k-1],dp[itwo][k+1]);
                }
            }
            m++;
        } else if (s[i] == '+'){
            FOR(k,50010-m,50010+m+1){
                    dp[itwo^1][k] = dp[itwo][k] + k - 50010;
            }
        } else {
            FOR(k,50010-m,50010+m+1){
                    dp[itwo^1][k] = dp[itwo][k] - k + 50010;
            }
        }
    }
    printf("%lld\n",dp[itwo^1][50010] - ((int64_t)1<<40));
}

Submission Info

Judge Result