結果

問題 No.3144 Parentheses Modification and Rotation (01 Ver.)
ユーザー Leal-0
提出日時 2025-05-16 23:10:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,476 bytes
コンパイル時間 2,489 ms
コンパイル使用メモリ 201,088 KB
実行使用メモリ 16,072 KB
最終ジャッジ日時 2025-05-16 23:10:56
合計ジャッジ時間 10,025 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 3 WA * 5 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__

int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;

    string s2=s+s; 
    vector<int> cum2(2*n+1,0); 
    rep(i,2*n) {
        cum2[i+1]=cum2[i]+(s2[i]=='(' ? 1 : -1);
    }

    int min_cost=iinf;
    rep(k,n) {
        int ch=0;
        int balance=0;
        int min_bal=0;

        srep(i,k,k+n-1)  {
            balance+=(s2[i]=='(' ? 1 : -1);
            min_bal=min(min_bal,balance);
        }

        int final=cum2[k+n]-cum2[k];
        if (final%2!=0) continue;
        if (min_bal<0)  ch+=(-min_bal+1)/2;

        if (final>0)  ch+=final/2;
        else  ch+=(-final)/2; 

        chmin(min_cost,ch);
    }

    cout<<min_cost<<nl;
    return 0;
}

/////// library zone ///////
#else
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define irep(i,r,l) for(ll i=r;i>=l;i--)
#define srep(i,l,r) for(ll i=l;i<=r;i++)
using ll = long long;
using ld = long double;
const ll mod=998244353;
#define vout(v) for(auto i :v) cout<<i<<" ";
#define INF 9223300000000000000ll
#define Winf 5e12
#define iinf 1e9
#define nl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vl vector<ll>
#define vc vector<char>

int calc_min(string &s) {
    stack<int> st;
    for(char c:s) {
        if(c=='(') {
            st.push(0);
        } else {
            int cur=st.top();
            st.pop();
            int score=(cur==0 ? 2 : cur+1);
            if(st.empty()) {
                st.push(score);
            } else {
                int prev=st.top();
                st.pop();
                st.push(prev+score);
            }
        }
    }
    return st.empty() ? 0:st.top();
}



template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}

void no() { cout<<"No"<<nl;}
void yes() { cout<<"Yes"<<nl;}
void yn(bool a) {
    cout<<(a ? "Yes":"No")<<nl;
}

ll sum(vector<ll>& a) {
    ll ans=0;
    for(auto i:a) ans+=i;
    return ans;
}




ll modpow(ll fl, ll po, ll mode) {  // mode: 0=modなし, 1=modあり
    ll ret=1;
    if (mode) {
        while (po>0) {
            if (po&1) ret=(ret*fl)%mod;
            fl=(fl*fl)%mod;
            po>>=1;
        }
    } else {
        while (po>0) {
            if(po&1) ret*=fl;
            fl*=fl;
            po>>=1;
        }
    }
    return ret;
}



#endif
0