Submission #1280578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280578		khoavn2008	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	313 ms	2272 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define FOR(i,l,r) for(ll i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(ll i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(ll i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define size(v) ((ll)(v).size())
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)

const ll N = 1e5 + 10, INF = 1e9, LOG = 21;
ll n,MOD;
string s;
void add(ll &a,ll b){
    a += b;
    if(a >= MOD) a %= MOD;
}
ll dp[2][MASK(5)][5][2];
bool check(ll mask,ll k){
    if(abs(k) >= 3)return 0;
    if(k + 3 <= 2 && BIT(mask, k + 3 + 2))return 0;
    if(k - 3 >= -2 && BIT(mask, k - 3 + 2))return 0;
    return 1;
}
int main(){
//    freopen(".INP", "r", stdin);
//    freopen(".OUT", "r", stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>MOD>>s;
    s = " " + s;
    dp[0][0][2][0]++;
    ll ans = 0;
    FOR(i,0,n){
        REP(mask,MASK(5))FOR(k,-2,2)REP(low,2)if(dp[0][mask][k + 2][low]){
//            cout<<i<<' '<<bitset<5>(mask)<<' '<<k<<' '<<low<<endl;
            if(i == n){
                add(ans, dp[0][mask][k + 2][low]);
                continue;
            }
            ll lim = low ? 1 : (s[i + 1] == 'L' ? 0 : 1);
            FOR(c,0,lim){
                ll nmask = mask | MASK(k + 2);
                ll nk = k + (c == 0 ? +1 : -1);
                if(!check(nmask, nk))continue;
                bool nlow = low || c != lim;
                add(dp[1][nmask][nk + 2][nlow], dp[0][mask][k + 2][low]);

            }
            dp[0][mask][k + 2][low] = 0;
        }
        swap(dp[0], dp[1]);
    }
    cout<<ans;
}
/*
12
10000
LPLLPLPPLPLL
*/

• 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