Submission #255309

#	Time	Username	Problem	Language	Result	Execution time	Memory
255309		shayan_p	parentrises (BOI18_parentrises)	C++14	100 / 100	220 ms	115192 KiB

parentrises

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 310, maxn2 = 1e6 + 10, mod = 1e9 + 7;

int dp[maxn][2 * maxn][maxn]; // n // 2o - c // o - 2c
int ans[maxn];
	     
void add(int &A, int B){
    A = (A + B) % mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int P, q;
    cin >> P >> q;
    
    if(P == 1){
	while(q--){
	    string s;
	    cin >> s;
	    int A = 0;
	    bool bad = 0;
	    for(int i = sz(s)-1; i >= 0; i--){
		A+= (s[i] == ')' ? 2 : -1);
		bad|= A < 0;
	    }
	    A = 0;
	    for(int i = 0; i < sz(s); i++){
		A+= (s[i] == '(' ? 2 : -1);
		bad|= A < 0;
	    }
	    if(bad){
		cout << "impossible\n";
		continue;
	    }
	    int pos = sz(s) - A;
	    string ans = s;
	    bool o = 0;
	    for(int i = 0; i < pos; i++){
		if(s[i] == '(')
		    ans[i] = 'G';
		else
		    ans[i] = (o ? 'R' : 'B'), o^=1;		
	    }
	    o = 0;
	    for(int i = sz(s)-1; i >= pos; i--){
		if(s[i] == ')')
		    ans[i] = 'G';
		else
		    ans[i] = (o ? 'R' : 'B'), o^=1;
	    }
	    cout << ans << "\n";
	}
    }
    if(P == 2){
	dp[0][0][0] = 1;
	for(int n = 0; n < maxn - 5; n++){
	    for(int sm = 0; sm <= 2 * n; sm++){
		for(int mx = 0; mx <= n; mx++){
		    add(dp[n + 1][sm + 2][max(int(0), mx + 1)], dp[n][sm][mx]);
		    if(sm > 0)
			add(dp[n+1][sm - 1][max(int(0), mx - 2)], dp[n][sm][mx]);
		}
		add(ans[n], dp[n][sm][0]);
	    }
	}
	while(q--){
	    int n;
	    cin >> n;
	    cout << ans[n] << "\n";
	}
    }
    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