oj.uz

Submission #900137

# Submission time Handle Problem Language Result Execution time Memory
900137 2024-01-07T17:54:24 Z JakobZorz Linear Garden (IOI08_linear_garden) C++17
100 / 100
 163 ms 14276 KB 
#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 dp1[5][3][3];
ll dp2[5][3][3];

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 (dp2[pref+1+2][-min_pref][max_pref]+dp2[pref-1+2][-min_pref][max_pref])%MOD;
}

void solve(){
    cin>>n>>MOD>>str;
    int pref=0,min_pref=0,max_pref=0;
    
    vector<int>prefv(n),min_prefv(n),max_prefv(n);
    
    for(int i=0;i<n;i++){
        prefv[i]=pref;
        min_prefv[i]=min_pref;
        max_prefv[i]=max_pref;
        if(str[i]=='P')
            pref++;
        else
            pref--;
        
        min_pref=min(min_pref,pref);
        max_pref=max(max_pref,pref);
    }
    
    ll res=1;
    
    for(int i=n-1;i>=0;i--){
        if(str[i]=='P'){
            res+=get(i+1,prefv[i]-1,min_prefv[i],max_prefv[i]);
            res%=MOD;
        }
        
        for(int i1=0;i1<5;i1++){
            for(int i2=0;i2<3;i2++){
                for(int i3=0;i3<3;i3++){
                    dp1[i1][i2][i3]=get(i+1,i1-2,-i2,i3);
                }
            }
        }
        
        memcpy(dp2,dp1,sizeof(dp1));
    }
    
    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
5
 
12 10000 LPLLPLPPLPLL
39
 
 */

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1116 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1372 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4524 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5688 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6892 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 8440 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 13304 KB Output is correct
2 Correct 163 ms 14128 KB Output is correct
3 Correct 139 ms 14276 KB Output is correct