Submission #1868429

---

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 = 1e7;

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;
    }
    dp[i][n + j] = res;
    return res;
}

int main() {
    cin >> s;
    n = s.length();
    if (n >= 1000) { cout << 0 << endl; return 0; }
    //fill(dp[0], dp[1010], -INF);

    dp[0][n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = -n/2; j < n+n/2; ++j) {
            if (s[i] == 'M') {
                dp[i][n+j] = min(dp[i+1][n+j+1], dp[i+1][n+j-1]);
            }
            else if (s[i] == '+') {
                dp[i][n+j] = dp[i+1][n+j] + j;
            }
            else if (s[i] == '-') {
                dp[i][n+j] = dp[i+1][n+j] - j;
            }
        }
    }
    cout << dp[0][n] * -1 << endl;
}

Submission Info

Judge Result