Submission #444552

#	Time	Username	Problem	Language	Result	Execution time	Memory
444552		rKrPaN	Linear Garden (IOI08_linear_garden)	C++14	75 / 100	245 ms	65540 KiB

linear_garden

#include <iostream>
#include <string>
#include <cstring>
#include <map>

using namespace std;

typedef long long ll;
const int MAXN = 1e6 + 6;

int n, m;
string s;
map <tuple <int, int, int, int>, int> memo;
//int memo[MAXN][5][5][2];

int sum(ll a, ll b){
    return a+b >= m? a+b-m : a+b;
}

int rek(int x, int lo, int hi, int da){
    if (x >= n)return 1;
    int znj = memo[make_tuple(x, lo+2, hi+2, da)];
    if (znj != 0)return znj;
    //if (memo[x][lo+2][hi+2][da] != -1)return memo[x][lo+2][hi+2][da];

    int ret = 0;
    if (da){
        ///P
        int lo1 = min(lo+1, 1), hi1 = max(hi+1, 1);
        if (lo1 >= -2 && hi1 <= 2)
            ret = sum(ret, rek(x+1, lo1, hi1, 1));
        ///L
        int lo2 = min(lo-1, -1), hi2 = max(hi-1, -1);
        if (lo2 >= -2 && hi2 <= 2)
            ret= sum(ret, rek(x+1, lo2, hi2, 1));

        //return memo[x][lo+2][hi+2][da] = ret;
        return memo[make_tuple(x, lo+2, hi+2, da)] = ret;
    } else {
        ///P
        if (s[x] == 'P'){
            int lo1 = min(lo+1, 1), hi1 = max(hi+1, 1);
            if (lo1 >= -2 && hi1 <= 2)
                ret = sum(ret, rek(x+1, lo1, hi1, 0));
        }
        ///L
        int lo2 = min(lo-1, -1), hi2 = max(hi-1, -1);
        if (lo2 >= -2 && hi2 <= 2){
            if (s[x] == 'P')ret = sum(ret, rek(x+1, lo2, hi2, 1));
            if (s[x] == 'L')ret = sum(ret, rek(x+1, lo2, hi2, 0));
        }
        //cout << x << " |" << lo << " " << hi << " " << da << " | " << ret << "\n";
        return memo[make_tuple(x, lo+2, hi+2, da)] = ret;
        //return memo[x][lo+2][hi+2][da] = ret;
    }
}

int main (){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> s;

    //memset(memo, -1, sizeof memo);

    cout << rek(0, 0, 0, 0) << "\n";

    return 0;
}

• 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: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5