Submission #1688557

---

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][10021],m,slen;
string s;

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

Submission Info

Judge Result