Submission #880211

#	Time	Username	Problem	Language	Result	Execution time	Memory
880211		abcvuitunggio	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	240 ms	14368 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
int n,m,c[1000001],mn[1000001],mx[1000001],res=1,cur,dp[2][5][5][5];
string s;
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    for (int i=0;i<5;i++)
        for (int j=0;j<5;j++)
            for (int k=j;k<5;k++)
                dp[0][i][j][k]=(i-j<=2&&j-k>=-2);
    cin >> n >> m >> s;
    s=' '+s;
    c[0]=mn[0]=mx[0]=2;
    for (int i=1;i<=n;i++){
        c[i]=c[i-1]+(s[i]=='L')-(s[i]!='L');
        mn[i]=min(mn[i-1],c[i]);
        mx[i]=max(mx[i-1],c[i]);
    }
    for (int l=n;l;l--){
        if (s[l]!='L'&&c[l]<3&&c[l]-mx[l-1]>=-4&&c[l]<=mn[l-1])
            res=(res+dp[cur][c[l]+2][min(mn[l-1],c[l]+2)][max(mx[l-1],c[l]+2)])%m;
        cur^=1;
        for (int i=0;i<5;i++)
            for (int j=0;j<5;j++)
                for (int k=j;k<5;k++){
                    if (i-j>2||i-k<-2){
                        dp[cur][i][j][k]=0;
                        continue;
                    }
                    dp[cur][i][j][k]=((i?dp[cur^1][i-1][min(j,i-1)][k]:0)+(i<4?dp[cur^1][i+1][j][max(k,i+1)]:0))%m;
                }
    }
    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