Submission #1868338

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

string s;
int n;
int dp[1010][2020];
const int INF = 1e8;

int dfs(int i, int j) {
    if (i >= n) {
        if (j == 0) return 0;
        else return -INF;
    }

    if (dp[i][n + j] > -INF) return dp[i][n + j];

    int res = -INF;

    if (s[i] == 'M') {
        res = max(dfs(i + 1, j + 1), dfs(i + 1, j -1));
    }
    else if (s[i] == '+') {
        res = dfs(i + 1, j) + j;
    }
    else if (s[i] == '-') {
        res = dfs(i + 1, j) - j;
    }

    return (dp[i][n + j] = res);
}

int main() {
    cin >> s;
    n = s.size();
    assert(n <= 1000);
    fill(dp[0], dp[1010], -INF);
    cout << dfs(0, 0) << endl;
}

Submission Info

Judge Result