Submission #217824

#	Time	Username	Problem	Language	Result	Execution time	Memory
217824		tatyam	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	591 ms	1556 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define name3(a,b,c,d,...) d
#define rep1(a) for(ll i = 0; i < a; i++)
#define rep2(i,a) for(ll i = 0; i < a; i++)
#define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)


ll m;
struct Modint{
    ll x = 0;
    Modint(){}
    Modint(ll a): x(a % m){}
    Modint operator+(Modint a) const { return Modint(*this) += a; }
    Modint& operator+=(Modint a){ x += a.x; if(x >= m) x -= m; return *this; }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n;
    string s;
    cin >> n >> m >> s;
    Modint dp1[5][5][5] = {}, dp2[5][5][5] = {};
    dp2[2][2][2] = 1;
    bool flag = 1;
    each(c, s){
        rep(5) rep(j, 5) if(j - i < 3) rep(k, 5) if((k ^ flag) & 1 && dp1[i][j][k].x){
            if(k < 4) dp1[i][max(j, k + 1)][k + 1] += dp1[i][j][k];
            if(k) dp1[min(i, k - 1)][j][k - 1] += dp1[i][j][k];
            dp1[i][j][k] = 0;
        }
        rep(5) rep(j, 5) if(j - i < 3) rep(k, 5) if((k ^ flag) & 1 && dp2[i][j][k].x){
            if(k < 4 && c == 'P') dp2[i][max(j, k + 1)][k + 1] += dp2[i][j][k];
            if(k && c == 'P') dp1[min(i, k - 1)][j][k - 1] += dp2[i][j][k];
            if(k && c == 'L') dp2[min(i, k - 1)][j][k - 1] += dp2[i][j][k];
            dp2[i][j][k] = 0;
        }
        flag = !flag;
    }
    Modint ans = 0;
    rep(5) rep(j, 5) if(j - i < 3) rep(k, 5) ans += dp1[i][j][k];
    ans += 1;
    cout << ans.x << endl;
}

• 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