Submission #754094

#	Time	Username	Problem	Language	Result	Execution time	Memory
754094		AndresRPerez	Linear Garden (IOI08_linear_garden)	C++17	0 / 100	53 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 = 5;

int n, m;
string s;

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

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

    for( int nxt = -1 ; nxt <= 1 ; nxt += 2 ){
        int newCurr = curr + nxt;
        int newLo = min( lo, newCurr );
        int newHi = max( hi, newCurr );
        if( newCurr < 0 or newCurr > 4 ) continue;
        if( newHi - newLo > 2 ) continue;
        ret += dp( left-1, newLo, newHi, 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 = 2, lo = 2, hi = 2;
    int ans = 0;
    for( int i = 0 ; i < n ; i ++ ){
        if( s[i] == 'P' ){
            int newCurr = curr-1;
            int newLo = min( lo, newCurr );
            int newHi = max( hi, newCurr );
            int add = dp( n-i-1, newLo, newHi, newCurr );
            //cout << "   -> add " << add << endl ;
            ans += add;
            ans %= m;
        }
        if( s[i] == 'L' ) curr --;
        else curr ++;
        lo = min( lo, curr );
        hi = max( hi, curr );
    }
    cout << ans+1 << endl ;

    return 0;
}

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