Submission #1036617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036617		VMaksimoski008	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	409 ms	11572 KiB

linear_garden

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int LOG = 20;
const int maxn = 1e5 + 5;

ll n, mod, ans = 0;
vector<ll> vec;
string s;

ll dp[2][5][5][5][2];

signed main() {
    cin >> n >> mod >> s;
    vec.push_back(0);

    for(int i=0; i<n; i++) {
        if(s[i] == 'L') vec.push_back(-1);
        else vec.push_back(1);
    }

    dp[0][2][2][2][0] = 1;
    for(int pos=0; pos<n; pos++) {
        for(int mn=0; mn<=4; mn++) {
            for(int mx=mn; mx<=min(4, mn+2); mx++) {
                for(int curr=mn; curr<=mx; curr++) {
                    for(int under=0; under<2; under++) {
                        for(int i=-1; i<=1; i++) {
                            if(i == 0) continue;
                            if(!under && i > vec[pos+1]) continue;
                            int nmn = min(mn, curr + i);
                            int nmx = max(mx, curr + i);
                            int nu = under | (i < vec[pos+1]);
                            if(nmx - nmn > 2 || nmn < 0 || nmx > 4) continue;
                            dp[1][nmn][nmx][curr+i][nu] = (dp[0][mn][mx][curr][under] + dp[1][nmn][nmx][curr+i][nu]) % mod;
                        }
                    }
                }
            }
        }

        for(int mn=0; mn<=4; mn++) {
            for(int mx=mn; mx<=4; mx++) {
                for(int curr=mn; curr<=mx; curr++) {
                    for(int under=0; under<2; under++) {
                        dp[0][mn][mx][curr][under] = dp[1][mn][mx][curr][under];
                        dp[1][mn][mx][curr][under] = 0;
                    }
                }
            }
        }
    }

    ll ans = 0;
    for(int mn=0; mn<=4; mn++)
        for(int mx=mn; mx<=min(4, mn+2); mx++)
            for(int curr=mn; curr<=mx; curr++) ans = (ans + dp[0][mn][mx][curr][1]) % mod;
    cout << (ans + 1) % mod << '\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: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5