| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 249231 | eohomegrownapps | Linear Garden (IOI08_linear_garden) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m;
int dpv[1000000][3];
int dp(int len, int s, int e, int cur){
//can we go up?
//cout<<len<<" "<<s<<" "<<e<<" "<<cur<<'\n';
if (!(s<=cur&&cur<=e)||(e-s>2)){
return 0;
}
if (e-s==2&&len%2==0%%dpv[len/2][cur-s]!=-1){
return dpv[len/2][cur-s];
}
if (len==0){
return 1;
}
if (e-s<2){
return (dp(len-1,min(s,cur-1),e,cur-1)+dp(len-1,s,max(e,cur+1),cur+1))%m;
} else {
if (len%2==0){
return dpv[len/2][cur-s]=((cur-1<s?0:dp(len-1,s,e,cur-1))+(cur+1>e?0:dp(len-1,s,e,cur+1)))%m;
} else {
return ((cur-1<s?0:dp(len-1,s,e,cur-1))+(cur+1>e?0:dp(len-1,s,e,cur+1)))%m;
}
}
}
void initdp(){
for (int i = 0; i<500000; i++){
//for (int j = 0; j<3; j++){
for (int k = 0; k<3; k++){
dpv[i][k]=-1;
}
//}
}
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
initdp();
int n;
cin>>n;
cin>>m;
int curmin = 0;
int curmax = 0;
int curval = 0;
ll ind = 1;
for (int i = 0; i<n; i++){
char c;
cin>>c;
bool val = (c=='P');
if (val){
ind+=dp(n-i-1,min(curmin,curval-1),max(curmax,curval-1),curval-1);
ind%=m;
curval++;
} else {
curval--;
}
curmin=min(curmin,curval);
curmax=max(curmax,curval);
}
cout<<ind<<'\n';
}