oj.uz

Submission #863300

# Submission time Handle Problem Language Result Execution time Memory
863300 2023-10-20T02:03:47 Z HuyQuang_re_Zero Linear Garden (IOI08_linear_garden) C++14
100 / 100
 156 ms 14116 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define rand(l,r) (l+rng()%(r-l+1))
#define f(cnt,mi,ma) f[cnt+2][mi+2][ma]
#define g(cnt,mi,ma) g[cnt+2][mi+2][ma]
using namespace std;
string s;
int Mi[N],Ma[N],Cnt[N],f[5][3][3],g[5][3][3],cnt,mi,ma,mod,n,i,res;
void update(int &a,int b)
{
    a+=b;
    if(a>=mod) a-=mod;
}
int main()
{
  //  freopen("linear_garden.inp","r",stdin);
    //freopen("linear_garden.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>mod>>s; s=" "+s;
    for(i=1;i<=n;i++)
    {
        Cnt[i]=Cnt[i-1]+(s[i]=='L')-(s[i]=='P');
        Mi[i]=min(Mi[i-1],Cnt[i]);
        Ma[i]=max(Ma[i-1],Cnt[i]);
    }
    for(cnt=-2;cnt<=2;cnt++)
        for(mi=-2;mi<=0;mi++)
            for(ma=0;ma<=2;ma++)
                if(ma-mi<=2) f(cnt,mi,ma)=1;
    for(i=n;i>=1;i--)
    {
        if(s[i]=='P' && Cnt[i-1]+1<=2)
            update(res,f(Cnt[i-1]+1,Mi[i-1],max(Ma[i-1],Cnt[i-1]+1)));
        for(cnt=-2;cnt<=2;cnt++)
            for(mi=-2;mi<=0;mi++)
                for(ma=0;ma<=2;ma++) g(cnt,mi,ma)=f(cnt,mi,ma),f(cnt,mi,ma)=0;
        for(cnt=-2;cnt<=2;cnt++)
            for(mi=-2;mi<=0;mi++)
                for(ma=0;ma<=2;ma++)
                {
                    if(cnt+1<=2) update(f(cnt,mi,ma),g(cnt+1,mi,max(ma,cnt+1)));
                    if(cnt-1>=-2) update(f(cnt,mi,ma),g(cnt-1,min(mi,cnt-1),ma));
                }
    }
    update(res,1);
    cout<<res;
}

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 344 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

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

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 464 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 344 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 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 348 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 4 ms 604 KB Output is correct

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

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

Subtask #19
5.0 / 5.0

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

Subtask #20
5.0 / 5.0

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

Subtask #21
5.0 / 5.0

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

Subtask #22
5.0 / 5.0

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

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 14116 KB Output is correct
2 Correct 145 ms 14112 KB Output is correct
3 Correct 144 ms 14112 KB Output is correct