Submission #887681

#	Time	Username	Problem	Language	Result	Execution time	Memory
887681		TNISL	Linear Garden (IOI08_linear_garden)	C++17	90 / 100	98 ms	65536 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=100000;
const int maxa=1e9;
const int base=311;
const ll inf=1e18;
const ll e=998244353;
int m, n;

void Add(int &x, int y){
    x+=y; x%=m;
}
void solve(){
    cin>>n>>m;
    string s;
    cin>>s;
    int a[n];
    memset(a,0,n);
    fou(i,0,n-1)
        a[i]=s[i]=='P';
    int f[n+3][5][5];//-2 -> 2
    memset(f,0,sizeof(f));
    f[n][2][2]=1;
    int ans=0;
    fod(i,n,1){
        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[i-1][l+2][r+2],f[i][x+2][y+2]);
                l=x+1, r=y+1;
                if(l>0) l=0;
                Add(f[i-1][l+2][r+2],f[i][x+2][y+2]);
            }
    }
    int mi=0, ma=0;
    fou(i,0,n-1){
        if(a[i]){
            fou(l,-2,2)
                fou(r,l,2){
                    if(l*r>0) continue;
                    if(l+mi-1>=-2 && r+ma-1<=2)
                        Add(ans,f[i+1][l+2][r+2]);
                }
        }
        if(a[i]) ++mi, ++ma;
        else --mi, --ma;
        if(ma<0) ma=0;
        if(mi>0) mi=0;
    }
    ++ans;
    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: 0 / 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: 0 / 5