Submission #63549

#	Time	Username	Problem	Language	Result	Execution time	Memory
63549		Bruteforceman	parentrises (BOI18_parentrises)	C++11	100 / 100	337 ms	219168 KiB

parentrises

#include "bits/stdc++.h"
using namespace std;
// vector <char> v[1000010];

string solve(string s) {
	int n = s.size();
	stack <int> p;
	stack <int> q;
	string ans;
	for(int i = 0; i < n; i++) ans += '#';
	for(int i = 0; i < n; i++) {
		if(s[i] == ')') {
			if(p.empty()) {
				if(q.empty()) return "impossible";
				else {
					ans[q.top()] = 'G';
					ans[i] = 'B';
					q.pop();
				}
			} else {
				ans[p.top()] = 'R';
				ans[i] = 'R';
				p.pop();
			}
		} else {
			p.push(i);
			q.push(i);
		}
	}
	stack <int> thic;
	for(int i = 0; i < n; i++) {
		if(ans[i] == '#') {
			thic.push(i);
		} else if (s[i] == ')' && !thic.empty()) {
			ans[thic.top()] = 'B';
			ans[i] = 'G';
			thic.pop();
		}
	}
	if(thic.empty()) return ans;
	else return "impossible";
}
const int mod = 1000000000 + 7;
int mem[301][301][301];
int fem[301][301][301];
int dp(int cur, int p, int q) {
	if(cur == 0) {
		return p == 0;
	}
	if(mem[cur][p][q] != -1) return mem[cur][p][q];
	int ans = 0;
	ans += dp(cur - 1, p + 1, q + 1);
	if(p > 0) ans += dp(cur - 1, p - 1, q);
	else if(q > 0) ans += dp(cur - 1, p, q - 1);
	ans %= mod;
	return mem[cur][p][q] = ans;
}
int fn(int cur, int p, int q) {
	if(cur == 0) {
		return q == 0;
	}
	if(fem[cur][p][q] != -1) return fem[cur][p][q];
	int ans = 0;
	ans += fn(cur - 1, p + 1, q + 1);
	if(p > 1) {
		ans += fn(cur - 1, p - 1, max(0, q - 2));
	}
	ans %= mod;
	return fem[cur][p][q] = ans;
}

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie(0);
	int p;
	cin >> p;
	int t;
	cin >> t;
	memset(mem, -1, sizeof mem);
	memset(fem, -1, sizeof fem);
	while(t--) {
		if(p == 1) {
			string s;
			cin >> s;
			cout << solve(s) << '\n';
		} else {
			int n;
			cin >> n;
			long long ans = 0;
			for(int i = 0; i <= n; i++) {
				ans += 1LL * dp(i, 0, 0) * fn(n-i, 0, 0);
				ans %= mod;
			}
			cout << ans << endl;
		}
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28