Submission #754097

#	Time	Username	Problem	Language	Result	Execution time	Memory
754097		AndresRPerez	Linear Garden (IOI08_linear_garden)	C++17	63 / 100	71 ms	65536 KiB

linear_garden

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+1;
const int M = 3;

int n, m;
string s;

int mem [N][M][M];

int dp( int left, int width, int curr ){
    if( left == 0 ) return 1;
    int &ret = mem[left][width][curr];
    if( ret != -1 ) return ret;
    
    ret = 0;

    for( int nxt = -1 ; nxt <= 1 ; nxt += 2 ){
        int newCurr = curr + nxt;
        int newWidth = width;
        if( newCurr < 0 ){
            newWidth ++;
            newCurr ++;
        }else if( newCurr > newWidth ){
            newWidth ++;
        }
        if( newWidth > 2 ) continue;
        ret += dp( left-1, newWidth, newCurr );
        ret %= m;
    }
    return ret;
}

int main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    memset(mem, -1, sizeof(mem));
    cin >> n >> m >> s ;
    
    int curr = 0, width = 0;
    int ans = 0;
    for( int i = 0 ; i < n ; i ++ ){
        if( s[i] == 'P' ){
            int newCurr = curr-1;
            int newWidth = width;
            if( newCurr < 0 ){
                newWidth ++;
                newCurr ++;
            }else if( newCurr > width ){
                newWidth ++;
            }
            int add = dp( n-i-1, newWidth, newCurr);
            //cout << "   -> add " << add << endl ;
            ans += add;
            ans %= m;
        }
        if( s[i] == 'L' ) curr --;
        else curr ++;
        if( curr < 0 ){
            width ++;
            curr ++;
        }else if( curr > width ){
            width ++;
        }
    }
    cout << ans+1 << endl ;

    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 0 / 4
• Subtask 11: 4 / 4
• Subtask 12: 0 / 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: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5