제출 #1089815

#제출 시각아이디문제언어결과실행 시간메모리
1089815peacebringer1667Linear Garden (IOI08_linear_garden)C++17
100 / 100
147 ms65388 KiB
#include<bits/stdc++.h> #define ll long long #define ldb long double #define fi first #define se second #define sza(a) (int)a.size() #define pir pair<int,int> #define pirll pair<ll,ll> using namespace std; const int maxn = 1e6 + 5; const int alp = 4; int modu; inline void add(int &x,int y){ x %= modu;y %= modu; x = (x + y) % modu; } int dp[maxn][alp][alp]; void prepare_dp(int n){ dp[n + 1][0][0] = 1; for (int p = n ; p > 0 ; p--){ for (int i = 0 ; i <= 2 ; i++) for (int j = 0 ; j <= 2 ; j++){ if (i < 2) add(dp[p][i + 1][max(j - 1,0)],dp[p + 1][i][j]); if (j <= 2) add(dp[p][max(i - 1,0)][j + 1],dp[p + 1][i][j]); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin >> n >> modu; prepare_dp(n); string s;cin >> s; int res = 0,p = 0,c1 = 0; for (char c : s){ p++; if (p > 1){ if (s[p - 2] == 'L') c1++; else c1 = max(0,c1 - 1); } if (c == 'P'){ for (int i = 0 ; i + c1 + 1 <= 2 ; i++) for (int j = 0 ; j <= 2 ; j++) add(res,dp[p + 1][i][j]); } } add(res,1); cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...