제출 #900129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900129		JakobZorz	Linear Garden (IOI08_linear_garden)	C++17	40 / 100	1567 ms	49476 KiB

linear_garden

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second
 
ll MOD;
int n;
string str;

ll get(int i,int pref,int min_pref,int max_pref){
    min_pref=min(min_pref,pref);
    max_pref=max(max_pref,pref);
    if(max_pref-min_pref>2)
        return 0;
    
    if(i==n)
        return 1;
    
    return (get(i+1,pref+1,min_pref,max_pref)+get(i+1,pref-1,min_pref,max_pref))%MOD;
}

void solve(){
    cin>>n>>MOD>>str;
    int pref=0,min_pref=0,max_pref=0;
    ll res=1;
    for(int i=0;i<n;i++){
        if(str[i]=='P'){
            res+=get(i+1,pref-1,min_pref,max_pref);
            res%=MOD;
            pref++;
        }else{
            pref--;
        }
        
        min_pref=min(min_pref,pref);
        max_pref=max(max_pref,pref);
    }
    cout<<res<<"\n";
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
 
14:
 
LLPLP
LLPPL
LPLLP
LPLPL
LPLPP
LPPLL
LPPLP
PLLPL
PLLPP
PLPLL
PLPLP
PLPPL
PPLLP
PPLPL
 
5 7 PLPPL
 
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: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 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