oj.uz

답안 #887690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887690 2023-12-15T03:00:08 Z TNISL Linear Garden (IOI08_linear_garden) C++17
100 / 100
 99 ms 14156 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+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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2616 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #7
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #9
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct

Subtask #10
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #11
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2652 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2652 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4952 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5116 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 9408 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 9572 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 9720 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 10128 KB Output is correct

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 13092 KB Output is correct
2 Correct 93 ms 14056 KB Output is correct
3 Correct 96 ms 14156 KB Output is correct