Submission #3369658

---

Source Code Expand

#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}

int imos[105];
int min_right[105];
int min_pos;
int min_all;
int ma;
vector<int> pos_minus;


int main(){
    cin.tie(0);

    string S; cin >> S;
    
    int ans = 0;
    for (int i = 0; i < S.length(); i++){
        if (S[i] == '(') imos[i] = 1;
        else imos[i] = -1;
        if (i){
            imos[i] += imos[i-1];
        }
        if (min_all > imos[i]){
            min_all = imos[i];
            min_pos = i;
        }
        if (S[i] == ')') pos_minus.push_back(i);
    }
    if (min_all < 0){
        ans += -(min_all-1)/2;
        ma = pos_minus[-(min_all-1)/2-1];
    }
    if (-imos[S.length()-1] == ans*2){
        cout << ans + ma << endl;
        return 0;
    }

    int x = imos[S.length()-1] + ans*2;
    min_right[S.length()-1] = imos[S.length()-1] + ans*2;
    for (int i = S.length()-2; i >= 0; i--){
        min_right[i] = min(min_right[i+1], imos[i] + ans*2);
    }
    for (int i = min_pos; i < S.length(); i++){
        if (x == min_right[i]){
            ma = i;
            break;
        }
    }
    ans += x/2;
    cout << ans + ma << endl;
} 

Submission Info

Judge Result