Submission #13118554

---

Source Code Expand

/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

// ref: https://codeforces.com/blog/entry/77148?#comment-619728

#include<bits/stdc++.h>
using namespace std;

#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)(x.size()))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     makep           make_pair
#define     maket           make_tuple
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)+(x)-1)/(x))
#define     gcd(a,b)        (__gcd((a),(b)))
#define     lcm(a,b)        ((a)*((b)/gcd((a),(b))))
#define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
#define     flush           fflush(stdout)
#define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ld pi=acos(-1);
const ll inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int n;
    cin>>n;

    vector<pii> pve,nve;

    string s;
    int cnt,len;
    pii p;
    for(int i=0;i<n;++i)
    {
        cin>>s;
        len=sz(s);

        cnt=0;
        for(int j=0;j<len;++j)
        {
            if(s[j]=='(')
                ++cnt;
            else if(cnt)
                --cnt;
        }
        p.S=cnt;        // unbalanced "("

        cnt=0;
        for(int j=len-1;j>=0;--j)
        {
            if(s[j]==')')
                ++cnt;
            else if(cnt)
                --cnt;
        }
        p.F=cnt;        // unbalanced ")"

        if(p.S-p.F>=0)
            pve.pb(p);
        else
            nve.pb(p);
    }

    sort(all(pve),[](pii a,pii b){return a.F<b.F;});
    sort(all(nve),[](pii a,pii b){return a.S>b.S;});

    vector<pii> a;
    a.reserve(n);
    a.insert(end(a),all(pve));
    a.insert(end(a),all(nve));

    int sum=0;
    for(auto c:a)
    {
        sum-=c.F;

        if(sum<0)
        {
            cout<<"No";
            return;
        }

        sum+=c.S;
    }

    if(sum)
        cout<<"No";
    else
        cout<<"Yes";
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}

Submission Info

Judge Result