Submission #1690505

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

long long int num[200000];

int main(){
	
	string str;
	cin >> str;
	int i;
	vector<int> v1, v2;
	
	int M_num = 0;
	for(i = 0; i < str.size(); i++){
		if(str[i] == 'M'){
			M_num++;
		}
	}
	
	int ind_h;
	int count = 0;
	for(i = 0; i < str.size(); i++){
		if(str[i] == 'M'){
			count++;
			if(count == M_num / 2 + 1){
				ind_h = i - 1;
				break;
			}
		}
	}
	
	int score = 0;
	for(i = ind_h; i >= 0; i--){
		if(str[i] == 'M'){
			v1.push_back(score);
		}else if(str[i] == '+'){
			score++;
		}else{
			score--;
		}
	}
	
	score = 0;
	for(i = ind_h + 1; i < str.size(); i++){
		if(str[i] == 'M'){
			v2.push_back(score);
		}else if(str[i] == '+'){
			score++;
		}else{
			score--;
		}
	}
	
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	
	long long int sum = 0;
	for(int i = 0; i < v1.size(); i++){
		sum += v1[i];
	}
	
	num[0] = sum;
	
	for(int i = 0; i < v1.size(); i++){
		sum -= v1[i] * 2;
		num[i + 1] = sum;
	}
	
	long long int ans = 0;
	
	sum = 0;
	for(int i = 0; i < v2.size(); i++){
		sum += v2[i];
	}
	
	ans = max(ans, num[0] + sum);
	
	for(int i = 0; i < v2.size(); i++){
		sum -= v2[i] * 2;
		ans = max(ans, num[i + 1] + sum);
	}
	
	cout << ans << endl;
	
	return 0;
}

Submission Info

Judge Result