\(s_{i}\) を一つのブロックだと思って，ブロック単位で計算しても良い． ブロック \(s_{i}\) においての \(p_{i} := \) (min, 増加量)を持って計算すればよい． ブロックの結合に対応する演算は， \*1;
AtCoder Beginner Contest 167F
sort(rs.rbegin(), rs.rend());
yesno(tot == 0 && check(ls) && check(rs));
return 0;
}
*1:x,d) \cdot (y,e) = (min(x, d+y), d+e)\) となる．単位元は \(\,(-\infty, 0)\) ． \(p\) の先頭から \(i\) 個の積を \(q_{i}\) とおく．
正しい括弧列になる必要十分条件は， \(p_{i}\) の第一成分の和が0かつ 任意の\( i \in [1,N]\) に対して \(q_{i}\)の第二成分が0以上.
あとは， \(p_{i}\) の第2成分が正か負かで分けて，それぞれ貪欲に選んでいく． 正の方は，使えるブロックはすぐに使った方が得． ただし，負の方は反転処理を施して，正の場合に帰着する． \((x,d)\) を \(\,(x-d, -d)\) にする．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
cinv(s);
// min だけチェック．和が0は別でチェック．
ll h = 0;
for(pll p: ps){
auto [x,d] = p; // x : current min, // <min, diff>
ll b = h + x; // new min
if(b < 0) return false;
h += d;
}
return true;
};
// pll : <min, diff>
ll tot = 0;
rep(i,n){
// calc in block s[i] ------------------
// h is diff
// b is min
ll h = 0, b = 0;
for(char c: s[i]) {
if(c == '(') h++; else h--;
chmin(b, h);
}
//--------------------------------------
if(h > 0) ls.emplace_back(b, h);
else rs.emplace_back(b-h, -h);
tot += h;
}
sort(ls.rbegin(), ls.rend(
