Submission #312428

#	Time	Username	Problem	Language	Result	Execution time	Memory
312428		mohamedsobhi777	Linear Garden (IOI08_linear_garden)	C++14	31 / 100	234 ms	65536 KiB

linear_garden

#include<bits/stdc++.h>


#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 3e5 + 7 ; 
const ll inf = 2e18 ; 

// How interesting!

int n, mod,ans;

int dp[N][3][3][3] ; 
int pref_cur[N], prefA[N], prefB[N] ; 

string s ;
void normalize(int &a ,  int &b , int &A , int &B){
        int mn = min(a , b) ; 
        a-=mn ; b-=mn ; 
        A = min(A , a - b + 2); 
        B = max(B , a - b + 2);  
} 

inline int add(int x, int y){return x + y >= mod ? x + y - mod : x + y ;}

int solve(int i , int cur ,int A , int B){
        if(abs(A - B) > 2)return 0 ; 
        if(i == n)return 1 ; 
        if(~dp[i][cur][A][B])
                return dp[i][cur][A][B] ; 
        int ret = 0 ; 

        ret = add(ret , solve(i + 1, cur + 1, A , max(B , cur + 1) ) ) ; 
        ret = add(ret , solve(i + 1, cur - 1, min(A , cur - 1) , B ) ) ;

        return dp[i][cur][A][B] = ret; 
}

int main(){
        ios_base::sync_with_stdio(0) ;
        cin.tie(0) ; 
        //freopen("in.in" , "r" , stdin) ; 
        memset(dp , -1 , sizeof dp) ; 
        cin >> n >> mod >> s ; 

        for(int i = 0 ;i < n; ++ i){
                pref_cur[i] = (i ? pref_cur[i-1] : 0) + (s[i] == 'L' ? 1 : -1)  ; 
                prefA[i] = min( (i ? prefA[i-1] : (int)2) , pref_cur[i] + 2 ) ;
                prefB[i] = max( (i ? prefB[i-1] : 2) , pref_cur[i] + 2 ) ;  
        }

        for(int i = 0 ; i < n; ++ i){
                if(s[i] == 'P'){ // 0 
                        int a0 = (i?pref_cur[i-1]+1:2);
                        int A0 = (i?prefA[i-1]:3);
                        int B0 = (i?max( pref_cur[i-1] + 1 + 2 ,prefB[i-1]):2) ;
                        ans = add(ans , solve(i + 1, a0 , A0 , B0) ) ; 
                }
        }

        cout<< ++ ans % mod ; 
        return 0 ; 
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 4 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 4 / 4
• Subtask 11: 0 / 4
• Subtask 12: 5 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 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