Submission #1232905

#TimeUsernameProblemLanguageResultExecution timeMemory
1232905lanaskaricaLinear Garden (IOI08_linear_garden)C++20
95 / 100
55 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 + 5; string s; int n, MOD, dp[MAXN][3][3][2]; int add(int a, int b) { a += b; if (a >= MOD) a -= MOD; if (a < 0) a += MOD; return a; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); 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]); } } } //for (int i = 1; i <= n; i++) { //for (int j = 0; j < 3; j++) { //for (int z = 0; z < 3; z++) { //for (int r = 0; r < 2; r++) cout << "ispis: " << i << " " << j << " " << z << " " << r << " " << dp[i][j][z][r] << endl; //} //} //} //for (int i = 1; i <= n; i++) { //int zb = 0; //for (int j = 0; j < 3; j++) { //for (int z = 0; z < 3; z++) { //for (int r = 0; r < 2; r++) zb += dp[i][j][z][r]; //} //} //cout << zb << "\n"; //} 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...