제출 #580287

#제출 시각아이디문제언어결과실행 시간메모리
580287tranxuanbachLinear Garden (IOI08_linear_garden)C++17
41 / 100
21 ms14108 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define endl '\n' #define fi first #define se second #define For(i, l, r) for (auto i = (l); i < (r); i++) #define ForE(i, l, r) for (auto i = (l); i <= (r); i++) #define FordE(i, l, r) for (auto i = (l); i >= (r); i--) #define Fora(v, a) for (auto v: (a)) #define bend(a) (a).begin(), (a).end() #define isz(a) ((signed)(a).size()) using ll = long long; using ld = long double; using pii = pair <int, int>; using vi = vector <int>; using vpii = vector <pii>; using vvi = vector <vi>; const int N = 1e6 + 5; int mod; inline void sadd(int &x, int y){ if ((x += y) >= mod){ x -= mod; } } inline int add(int x, int y){ if ((x += y) >= mod){ x -= mod; } return x; } inline void ssub(int &x, int y){ if ((x -= y) < 0){ x += mod; } } inline int sub(int x, int y){ if ((x -= y) < 0){ x += mod; } return x; } int n; string s; int dp[3][N]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("KEK.inp", "r", stdin); // freopen("KEK.out", "w", stdout); cin >> n >> mod; dp[-1 + 1][0] = 1; dp[0 + 1][0] = 1; dp[1 + 1][0] = 1; ForE(i, 1, n){ ForE(d, -1, 1){ if (d >= 0){ sadd(dp[d + 1][i], dp[d - 1 + 1][i - 1]); } if (d <= 0){ sadd(dp[d + 1][i], dp[d + 1 + 1][i - 1]); } } } cin >> s; int d = 0, mxd = 0, mnd = 0, ans = 1; For(i, 0, n){ if (s[i] == 'P'){ d--; int tmxd = max(mxd, d), tmnd = min(mnd, d); if (-2 <= tmnd and tmxd <= 0){ sadd(ans, dp[(d + 1) + 1][n - i - 1]); } if (-1 <= tmnd and tmxd <= 1){ sadd(ans, dp[d + 1][n - i - 1]); } if (0 <= tmnd and tmxd <= 2){ sadd(ans, dp[(d - 1) + 1][n - i - 1]); } if (-1 <= tmnd and tmxd <= 0){ ssub(ans, 1); } if (0 <= tmnd and tmnd <= 1){ ssub(ans, 1); } d++; } if (s[i] == 'L'){ d--; } else{ d++; } mxd = max(mxd, d); mnd = min(mnd, d); } cout << ans << endl; } /* ==================================================+ INPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ */
#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...