Submission #236011

#	Time	Username	Problem	Language	Result	Execution time	Memory
236011		nicolaalexandra	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	145 ms	37556 KiB

linear_garden

#include <bits/stdc++.h>
#define DIM 1000010
using namespace std;

char v[DIM];
int dp[DIM][3][3];
int n,MOD,i,j,x,y;

int modul (int n){
    if (n < 0)
        return -n;
    return n;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>MOD>>v+1;

    /// dp[i][dif_mini][dif_maxi]

    /*for (i=0;i<=2;i++)
        for (j=0;j<=2;j++)
            dp[n+1][i][j] = 1;
    */
    dp[n+1][0][0] = 1;

    for (i=n+1;i>1;i--)
        for (int dif_min=0;dif_min<=2;dif_min++)
            for (int dif_max=0;dif_max<=2;dif_max++){
                if (dif_min != 2)
                    dp[i-1][dif_min+1][max(dif_max-1,0)] = (dp[i-1][dif_min+1][max(dif_max-1,0)] + dp[i][dif_min][dif_max]) % MOD;
                if (dif_max != 2)
                    dp[i-1][max(dif_min-1,0)][dif_max+1] = (dp[i-1][max(dif_min-1,0)][dif_max+1] + dp[i][dif_min][dif_max]) % MOD;
            }

    int mini = 0, maxi = 0, sol = 1;
    for (i=1;i<=n;i++){

        if (v[i] == 'P'){
            /// cate configuratii o sa am daca as pune L aici
            int mini_aux = mini + 1, maxi_aux = max (maxi - 1, 0);
            if (mini_aux <= 2){
                //sol = (sol + dp[i+1][mini_aux+2][maxi_aux]) % MOD;

                for (int x=0;x<=2;x++)
                    for (int y=0;y<=2;y++)
                        if (mini_aux + x <= 2 && maxi_aux + y <= 2)
                            sol = (sol + dp[i+1][x][y]) % MOD;
            }
        }

        if (v[i] == 'L'){
            mini++;
            maxi = max (maxi-1,0);
        } else {
            mini = max (mini-1,0);
            maxi++;
        }
    }

    cout<<sol;

    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:19:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin>>n>>MOD>>v+1;
                  ~^~

• 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