Submission #1690504

---

Source Code Expand

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <math.h>
#include <queue>
#include <stack>
#include <string>
#include <vector>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n - 1); i >= 0; --i)
#define D(n, retu)                                                             \
  REP(i, n) { cin >> retu[i]; }
#define mod 1000000007
#define INF 93193111451418101
#define MIN -933111451418101
//#define INF 931931114518101
using namespace std;
typedef pair<ll, ll> P;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
#define yo 100001
//------------------変数-----------------------//
ll n, maxmove = 0, movesize;
string s;
ll imos[114514], dp[114514];
//-------------------関数----------------------//

ll DP(ll num, ll lef, ll righ) {
  if (num == maxmove) {
    if (max(lef, righ) > maxmove / 2) {
      return MIN;
    }
    return 0;
  }
  if (dp[num] >= 0) {
    return dp[num];
  }
  if (max(lef, righ) > maxmove / 2) {
    return MIN;
  }
  ll hoge = max(DP(num + 1, lef + 1, righ) - imos[num],
                DP(num + 1, lef, righ + 1) + imos[num]);
  //  cout << num << " " << hoge << endl;
  return dp[num] = hoge;
}

int main() {
  // cout << "a" << endl;
  cin >> s;
  memset(dp, -1, sizeof(dp));
  REP(i, s.size()) {
    if (s[i] == 'M') {
      maxmove++;
    }
  }
  ll izryt = 0, nowpoint = s.size() - 1;
  for (ll i = maxmove - 1; i >= 0; i--) {
    while (1) {
      if (s[nowpoint] == 'M') {
        nowpoint--;
        imos[i] = izryt;
        break;
      }
      if (s[nowpoint] == '+') {
        izryt++;
      } else {
        izryt--;
      }
      nowpoint--;
    }
  }
  //  REP(i, s.size()) { cout << imos[i] << endl; }
  cout << DP(0, 0, 0) << endl;

  return 0;
}

Submission Info

Judge Result