Submission #255155

#	Time	Username	Problem	Language	Result	Execution time	Memory
255155		Saboon	parentrises (BOI18_parentrises)	C++14	100 / 100	311 ms	214648 KiB

parentrises

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 10;
const int N = 300 + 2;
const int mod = 1e9 + 7;
int l[maxn], r[maxn];
int dp[N][N][2*N], sumdp[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int type;
	cin >> type;
	if (type == 1){
		int tc;
		cin >> tc;
		while (tc --){
			string s;
			cin >> s;
			int L = 0, R = 0;
			int n = s.size();
			bool flag = 0;
			for (int i = n-1; i >= 0; i--){
				if (s[i] == ')')
					L ++, R += 2;
				else{
					if (R == 0){
						flag = 1;
						break;
					}
					L = max(0, L-2);
					R --;
				}
				l[i] = L, r[i] = R;
			}
			if (flag == 1 or L > 0){
				cout << "impossible\n";
				continue;
			}
			l[n] = r[n] = 0;
			int now = 0;
			bool Red1 = 1, Red2 = 1; 
			for (int i = 0; i < n; i++){
				if (s[i] == '('){
					if (l[i+1] <= now+1 and now+1 <= r[i+1]){
						if (Red1)
							cout << 'R';
						else
							cout << 'B';
						Red1 ^= 1;
						now ++;
					}
					else{
						cout << 'G';
						now += 2;
					}
				}
				else{
					if (l[i+1] <= now-1 and now-1 <= r[i+1]){
						if (Red2)
							cout << 'R';
						else
							cout << 'B';
						Red2 ^= 1;
						now --;
					}
					else{
						cout << 'G';
						now -= 2;
					}
				}
			}
			cout << '\n';
		}
	}
	else{
		int n = 300;
		dp[0][0][0] = 1;
		for (int i = 0; i < n; i++){
			for (int l = 0; l <= n; l++){
				for (int r = l; r <= 2*n; r++){
					dp[i+1][l+1][r+2] = (dp[i+1][l+1][r+2] + dp[i][l][r]) % mod;
					if (r > 0)
						dp[i+1][max(0,l-2)][r-1] = (dp[i+1][max(0,l-2)][r-1] + dp[i][l][r]) % mod;
				}
			}
		}
		for (int i = 1; i <= n; i++)
			for (int r = 0; r <= 2*n; r++)
				sumdp[i] = (sumdp[i] + dp[i][0][r]) % mod;
		int tc;
		cin >> tc;
		while (tc --){
			int n;
			cin >> n;
			cout << sumdp[n] << '\n';
		}
	}
}

• 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