Submission #863300

#	Time	Username	Problem	Language	Result	Execution time	Memory
863300		HuyQuang_re_Zero	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	156 ms	14116 KiB

linear_garden

#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 / 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