oj.uz

답안 #887687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887687 2023-12-15T02:53:17 Z TNISL Linear Garden (IOI08_linear_garden) C++17
0 / 100
 100 ms 14284 KB 
#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][y]);
            }
        }
        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
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 9408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 9572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 10132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 14284 KB Output isn't correct
2 Halted 0 ms 0 KB -