【題解】AtCoder ABC 167F – Bracket Sequencing

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 1000005;
int n, lmn[maxn], ladd[maxn];
string s;
vector <int> pl, mi;

bool cmp(int x, int y){
    if (lmn[x] != lmn[y]) return lmn[x] > lmn[y];
    else return ladd[x] > ladd[y];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s;
        int mn = 0, tot = 0;
        for (int j = 0; j < s.length(); j++){
            if (s[j] == '(') tot++;
            else tot--;
            mn = min(mn, tot);
        }
        lmn[i] = mn;
        ladd[i] = tot;
        if (tot >= 0) pl.push_back(i);
        else{
            mi.push_back(i);
            int mn = 0, tot = 0;
            for (int j = s.length()-1; j >= 0; j--){
                if (s[j] == ')') tot++;
                else tot--;
                mn = min(mn, tot);
            }
            lmn[i] = mn;
            ladd[i] = tot;
        }
    }
    sort(pl.begin(), pl.end(), cmp);
    sort(mi.begin(), mi.end(), cmp);
    int tot = 0;
    bool flag = true;
    for (int i:pl){
        if (tot + lmn[i] < 0) flag = false;
        tot += ladd[i];
        if (tot < 0) flag = false;
    }
    int tot2 = 0;
    for (int i:mi){
        if (tot2 + lmn[i] < 0) flag = false;
        tot2 += ladd[i];
        if (tot2 < 0) flag = false;
    }
    if (tot != tot2) flag = false;
    if (!flag) cout << "No\n";
    else cout << "Yes\n";
}