I'm trying to solve atcoder ABC167F. https://atcoder.jp/contests/abc167/tasks/abc167_f .

I started by questioning what conditions decide whether a concatenation is valid. We start by defining sum of a bracketed sequence, which is count('(')-count(')'). I then found the sum of every string, and the smallest sum of a prefix of the string. They are denoted by $$$sum$$$ and $$$mnprefix$$$ in my code. If my current string is valid which is equivalent to $$$mnprefix\ge 0$$$ and has a sum of $$$x$$$, then a concatenation is valid if and only if $$$x+mnprefix\ge 0$$$ and our new sequnce has a sum of $$$x+sum$$$. Let's say we have two strings $$$a$$$ and $$$b$$$. Let $$$a.sum$$$ denote the sum of $$$a$$$ and the rest of the notation is deductible.

Let's say $$$a$$$ comes before $$$b$$$. Then the two conditions that need to be valid are $$$x\ge a.mnprefix$$$ and $$$x\ge b.mnprefix-a.sum$$$. So we want $$$\max(a.mnprefix, b.mnprefix-a.sum)\le \max(b.mnprefix, a.mnprefix - b.sum)$$$ for $$$a$$$ to be chosen before $$$b$$$. However my proof has one flaw, which is that it doesn't account for transitivity. I don't know how to prove another string $$$c$$$ will not affect my result, and how do I know my comparator function is transitive, as each string doesn't have an exact value, and the comparator values are differing according to the string being compared to.

If my solution is correct, can someone tell me if I have made an error in my implementation.

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb emplace_back
#define vi vector<int>
using namespace std;
struct brackets{
    int mnprefix, sum;
    brackets(const string &s){
        mnprefix=0;
        sum=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                sum++;
            }
            if(s[i]==')'){
                --sum;
            }
            mnprefix=min(mnprefix, sum);
        }
    }
    bool operator<(const brackets &y){
        return max(mnprefix, y.mnprefix-sum) < max(y.mnprefix, mnprefix - y.sum);
    }
};
void solve(){
    int n;
    cin>>n;
    vector<brackets> seq;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        seq.pb(brackets(s));
    }
    sort(seq.begin(), seq.end());
    int currsum=0;
    for(int i=0;i<n;i++){
        if(currsum+seq[i].mnprefix<0){
            cout<<"No\n";
            return;
        }
        currsum+=seq[i].sum;
    }
    if(currsum!=0){
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
//17/32 correct