Submission #171013

#	Time	Username	Problem	Language	Result	Execution time	Memory
171013		dantoh000	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	294 ms	17028 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
int dp[2][5][5][5];
int l[1000005], r[1000005], m[1000005];
int n,mod;
int a[1000005];
int main(){
    scanf("%d%d",&n,&mod);
    l[0] = r[0] = m[0] = 2;
    for (int i = 1; i <= n; i++){
        char x;
        scanf(" %c",&x);
        a[i] = (x=='L')?-1:1;
        m[i] = m[i-1] + a[i];
        l[i] = min(l[i-1],m[i]);
        r[i] = max(r[i-1],m[i]);
    }
    int ans = 1;
    for (int i = n; i >= 0; i--){
        if (i == n){
            for (int L = 0; L <= 4; L++){
                for (int R = 0; R <= 4; R++){
                    for (int M = 0; M <= 4; M++){
                        if (L <= M && M <= R && R - L <= 2) dp[n&1][L][R][M] = 1;
                    }
                }
            }
            goto calc;
        }
        for (int L = 0; L <= 2; L++){
            for (int R = 2; R <= 4; R++){
                for (int M = 0; M <= 4; M++){
                    dp[i&1][L][R][M] = 0;
                    if (L <= M && M <= R && R - L <= 2){
                        if (R-min(L,M-1) <= 2){
                            dp[i&1][L][R][M] += dp[1-i&1][min(L,M-1)][R][M-1];
                            dp[i&1][L][R][M] %= mod;
                        }
                        if (max(R,M+1)-L <= 2){
                            dp[i&1][L][R][M] += dp[1-i&1][L][max(R,M+1)][M+1];
                            dp[i&1][L][R][M] %= mod;
                        }
                        //printf("%d %d %d %d %d\n",i,L,R,M,dp[i&1][L][R][M]);
                    }
                }
            }
        }
        calc:;
        if (a[i] == 1){
            int nL = min(l[i-1],m[i-1]-1);
            int nM = m[i-1]-1;
            int nR = r[i-1];
            if (nR-nL <= 2){
                //printf("if takes -1 for %d, %d %d %d\n",i,nL,nR,nM);
                //printf("num ways dp(%d %d %d %d) = %d\n",i,nL,nR,nM,dp[i&1][nL][nR][nM]);
                ans += dp[i&1][nL][nR][nM];
                ans %= mod;
            }
        }

    }
    printf("%d",ans);

}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:36:53: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
                             dp[i&1][L][R][M] += dp[1-i&1][min(L,M-1)][R][M-1];
                                                    ~^~
linear_garden.cpp:40:53: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
                             dp[i&1][L][R][M] += dp[1-i&1][L][max(R,M+1)][M+1];
                                                    ~^~
linear_garden.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&mod);
     ~~~~~^~~~~~~~~~~~~~~~
linear_garden.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&x);
         ~~~~~^~~~~~~~~~

• 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