Submission #13126173

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

const int N = 1e6 + 1;
bool taken[N];

bool cmp(pair<int, int> a, pair<int, int> b) {
	if(a.second == b.second)
		return a.first > b.first;
	return a.second < b.second;
}

bool cmp2(pair<int, int> a, pair<int, int> b) {
	if(a.first - a.second == b.first - a.second)
		return a.second < b.second;
	return a.first - a.second > b.first - a.second;
//	if(a.second == b.second)
//		return a.first > b.first;
//	return a.second > b.second;
}

int main() {
	fastIO;
#ifdef LOCAL
	freopen("input.in", "rt", stdin);
#endif
	int n;
	cin >> n;
	string str;
	int open = 0, closed = 0;
	vector<pair<int, int>> vec;
	for (int i = 0; i < n; ++i) {
		cin >> str;
		int cnt = 0, minus = 0;
		for (int i = 0; i < (int)str.size(); ++i) {
			if(str[i] == '(')
				++cnt;
			else
				--cnt;
			if(cnt < 0)
				++minus, cnt = 0;
		}
		if(minus) {
			if(cnt)
				vec.push_back({cnt, minus});
			else
				closed += abs(minus);
		} else {
			open += cnt;
		}
	}
	int total = open;
	sort(vec.begin(), vec.end(), cmp);
	for (int i = 0; i < (int)vec.size(); ++i) {
		if(vec[i].second > vec[i].first) continue;
		if(total >= vec[i].second) {
			total -= vec[i].second;
			total += vec[i].first;
			taken[i] = 1;
		}
	}
	vector<pair<int, int>> vv;
	for (int i = 0; i < (int)vec.size(); ++i) {
		if(taken[i]) continue;
		vv.push_back(vec[i]);
	}
	sort(vv.begin(), vv.end(), cmp2);
	for (int i = 0; i < (int)vv.size(); ++i) {
		total -= vv[i].second;
		if(total < 0) {
			cout << "No";
			return 0;
		}
		total += vv[i].first;
	}
	total -= closed;
	if(total == 0)
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

Submission Info

Judge Result