제출 #1232908

#제출 시각아이디문제언어결과실행 시간메모리
1232908lanaskaricaLinear Garden (IOI08_linear_garden)C++20
95 / 100
53 ms71908 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair <int, int> #define fi first #define se second const int MAXN = 1e6 + 1; int MOD, dp[MAXN][3][3][2]; int add(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); string s; int n; cin >> n >> MOD >> s; dp[1][1][0][0] = 1; dp[1][0][1][1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= 2; j++) { dp[i][j][0][0] = dp[i - 1][j - 1][0][0]; dp[i][0][j][1] = dp[i - 1][0][j - 1][1]; for (int z = 0; z <= 1; z++) { dp[i][j][z][0] = add(dp[i][j][z][0], dp[i - 1][j - 1][z + 1][0]); dp[i][j][z][0] = add(dp[i][j][z][0], dp[i - 1][j - 1][z + 1][1]); dp[i][z][j][1] = add(dp[i][z][j][1], dp[i - 1][z + 1][j - 1][0]); dp[i][z][j][1] = add(dp[i][z][j][1], dp[i - 1][z + 1][j - 1][1]); } } } int rj = 0, x = 0, y = 0; for (int i = 0; i < n; i++) { if (s[i] == 'L') { x++; y = max(0, y - 1); continue; } for (int j = 0; j <= (2 - x); j++) { for (int z = 0; z <= (2 - y); z++) { rj = add(rj, dp[n - i][j][z][0]); } } x = max(0, x - 1); y++; } cout << add(rj, 1) << "\n"; 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...