Submission #1690146

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#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 -93193111451418101
//#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 == movesize){ return 0; }
	if (dp[num]){ return dp[num]; }
	if (min(lef, righ) > maxmove){
		return -INF;
	}
	return dp[num] = max(DP(num + 1, lef + 1, righ) - imos[num], DP(num + 1, lef, righ + 1) + imos[num]);

}

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

	return 0;
}

Submission Info

Judge Result