Submission #1688537

---

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

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

Submission Info

Judge Result