• Source
    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. typedef long long ll;
    4. int main()
    5. {
    6. ios::sync_with_stdio(false);
    7. cin.tie(0);
    8. ll i,j;
    9. ll t;
    10. vector <ll> a;
    11. cin>>t;
    12. while(t--)
    13. {
    14. char s[100005];
    15. cin>>s;
    16. ll open=0,close=0,flag1=0,flag=0,m=0;
    17. for(i=0;s[i]!='\0';i++)
    18. {
    19. open+=(s[i]=='(');
    20. close+=(s[i]==')');
    21. if(open<close)
    22. flag=1;
    23. m++;
    24. }
    25. ll open1=0,close1=0;
    26. for(i=m-1;i>=0;i--)
    27. {
    28. open1+=(s[i]=='(');
    29. close1+=(s[i]==')');
    30. if(open1>close1)
    31. flag1=1;
    32. }
    33. ll r=open-close;
    34. if(flag==1 and flag1==1)
    35. continue;
    36. //cout<<t<<" "<<r<<"\n";
    37. a.push_back(r);
    38. }
    39. if(a.size()>1)
    40. sort(a.begin(),a.end());
    41. i=0;
    42. j=a.size()-1;
    43. ll ans=0;
    44.  
    45. while(i<j)
    46. {
    47. if(a[i]+a[j]==0)
    48. {
    49. ans++;
    50. i++;
    51. j--;
    52. }
    53. else if(a[i]+a[j]>0)
    54. {
    55. j--;
    56. }
    57. else
    58. {
    59. i++;
    60. }
    61. }
    62. cout<<ans;
    63. }
    64.