Submission #887690

#	Time	Username	Problem	Language	Result	Execution time	Memory
887690		TNISL	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	99 ms	14156 KiB

linear_garden

#include<bits/stdc++.h>
using namespace std;

#define fou(i,a,b) for(int i=(a);i<=(b);++i)
#define fod(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define endl "\n"
#define fi first
#define se second
#define bit(i,x) ((x>>i)&1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,int> lli;

const int nmax=1e6;
const int maxa=1e9;
const int base=311;
const ll inf=1e18;
const ll e=998244353;
int m, n;

int f[2][5][5];
int a[nmax+1];
int mi[nmax+1], ma[nmax+1];
void Add(int &x, int y){
    x+=y; x%=m;
}
void solve(){
    cin>>n>>m;
    string s;
    cin>>s;
    s="+"+s;
    fou(i,1,n){
        a[i]=s[i]=='P';
        if(a[i]) ma[i]=ma[i-1]+1, mi[i]=mi[i-1]+1;
        else ma[i]=ma[i-1]-1, mi[i]=mi[i-1]-1;
        if(ma[i]<0) ma[i]=0;
        if(mi[i]>0) mi[i]=0;
    }

    f[1][2][2]=1;
    int cur=1, next=0;
    int ans=0;
    fod(i,n+1,2){
        fou(x,-2,2)
            fou(y,x,2){
                if(x*y>0) continue;
                int l=x-1, r=y-1;
                if(r<0) r=0;
                Add(f[next][l+2][r+2],f[cur][x+2][y+2]);
                l=x+1, r=y+1;
                if(l>0) l=0;
                Add(f[next][l+2][r+2],f[cur][x+2][y+2]);
            if(a[i-1]){
                if(mi[i-2]+x-1>=-2 && ma[i-2]+y-1<=2)
                    Add(ans,f[cur][x+2][y+2]);
            }
        }
        swap(next,cur);
        memset(f[next],0,sizeof(f[next]));
    }
    Add(ans,1);
    cout<<ans;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
  //  freopen(".inp", "r", stdin);
   // freopen(".out", "w", stdout);

    solve();
    return 0;
}

• 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