Submission #1090647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090647		noyancanturk	parentrises (BOI18_parentrises)	C++17	100 / 100	99 ms	106712 KiB

parentrises

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int lim=301;
const int mod=1e9+7;

int sum(int i,int j){
  if(i+j<mod)return i+j;
  return i+j-mod;
}

void solve1(){
  string s;
  cin>>s;
  int n=s.size();
  int ty[n]{};
  int haveemp=0;
  vector<int>pools[2];
  for(int i=0;i<n;i++){
    if(s[i]=='('){
      haveemp++;
    }else if(1<haveemp){
      pools[0].pb(i);
      haveemp-=2;
    }else if(haveemp){
      pools[1].pb(i);
      ty[i]=1;
      haveemp=0;
    }else if(pools[0].size()){
      int toconvert=pools[0].back();
      pools[0].pop_back();
      ty[toconvert]=ty[i]=1;
      pools[1].pb(i);
      pools[1].pb(toconvert);
    }else if(pools[1].size()){
      int toconvert=pools[1].back();
      pools[1].pop_back();
      ty[i]=2;
      ty[toconvert]=3;
    }else{
      cout<<"impossible\n";
      return;
    }
  }
  if(haveemp){
    cout<<"impossible\n";
    return;
  }
  int needgreen=0,needred=0,needblue=0;
  string ans=string(n,' ');
  for(int i=n-1;0<=i;i--){
    if(s[i]=='('){
      if(needgreen){
        ans[i]='G';
        needgreen--;
      }else if(needred){
        ans[i]='R';
        needred--;
      }else if(needblue){
        ans[i]='B';
        needblue--;
      }
    }else if(ty[i]==0){
      ans[i]='G';
      needred++,needblue++;
    }else if(ty[i]==1){
      ans[i]='G';
      needgreen++;
    }else if(ty[i]==2){
      ans[i]='B';
    }else{
      ans[i]='R';
      needgreen++;
    }
  }
  cout<<ans<<"\n"; 
}

int dp[lim][lim][lim];

void solve2(){
  int n;
  cin>>n;
  int ans=0;
  for(int i=0;i<lim;i++)
    ans=sum(ans,dp[n][0][i]);
  cout<<ans<<"\n";
}

int main(){
  #ifdef Local
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
  #endif
  int _;
  cin>>_;
  if(_==1){
    int t;
    cin>>t;
    while(t--)solve1();
  }else{
    dp[0][0][0]=1;
    for(int i=1;i<lim;i++){
      for(int j=0;j<lim;j++){
        for(int k=0;k<lim;k++){
          dp[i][j][k]=sum(j?dp[i-1][j-1][k]:0,2<k&&j+2<lim?dp[i-1][j+2][k-3]:0);
        }
      }
      for(int k=0;k<lim;k++){
        dp[i][0][k]=sum(dp[i][0][k],sum(k?dp[i-1][1][k-1]:0,k+1<lim?dp[i-1][0][k+1]:0));
      }
    }
    int t;
    cin>>t;
    while(t--)solve2();
  }
}

• 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