Submission #1112730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112730		doducanh	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	69 ms	65536 KiB

linear_garden

///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=1e6+1;
int mod;
int n;
string s;
int dp[maxn][4][4];
void sol(void){
    cin>>n>>mod;
    memset(dp,0,sizeof(dp));
    for(int i=n;i>=0;i--){
        for(int j=2;j>=0;j--){
            for(int k=2;k>=0;k--){
                if(i==n){
                    dp[i][j][k]=1;
                    continue;
                }
                dp[i][j][k]=(dp[i+1][max(j-1,0)][k+1]+dp[i+1][j+1][max(k-1,0)])%mod;
            }
        }
    }
    cin>>s;
    s=" "+s;
    int ans=0;
    int x=0,y=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='L'){
            x=x+1;
            y--;
            y=max(y,0);
        }
        else{
            (ans+=dp[i][x+1][max(y-1,0)])%=mod;
            y++;
            x--;
            x=max(x,0);
        }
    }
    cout<<(ans+1)%mod;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5