Submission #1259564

#TimeUsernameProblemLanguageResultExecution timeMemory
1259564mdobricLinear Garden (IOI08_linear_garden)C++20
100 / 100
24 ms36580 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1000005; int n, dp[maxn][3][3], m; string s; int add (int x, int y){ if (x + y >= m) return x + y - m; if (x + y < 0) return x + y + m; return x + y; } int main (void){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; cin >> s; dp[0][0][1] = 1; dp[0][0][2] = 1; dp[0][1][0] = 1; dp[0][1][1] = 1; dp[0][1][2] = 1; dp[0][2][0] = 1; dp[0][2][1] = 1; dp[0][2][2] = 1; for (int i = 1; i <= n; i++){ dp[i][0][1] = dp[i - 1][1][0]; dp[i][0][2] = dp[i - 1][1][1]; dp[i][1][0] = dp[i - 1][0][1]; dp[i][1][1] = add(dp[i - 1][0][2], dp[i - 1][2][0]); dp[i][1][2] = add(dp[i - 1][0][2], dp[i - 1][2][1]); dp[i][2][0] = dp[i - 1][1][1]; dp[i][2][1] = add(dp[i - 1][2][1], dp[i - 1][0][2]); dp[i][2][2] = add(dp[i - 1][1][2], dp[i - 1][2][1]); } int prije = 0; int sufl = 0, sufp = 0; for (int i = 0; i < s.size(); i++){ if (s[i] == 'L'){ sufl++; sufp = max(sufp - 1, 0); } else{ int staril = sufl, starip = sufp; sufl++; sufp = max(sufp - 1, 0); if (sufl <= 2 and sufp <= 2)prije = add(prije, dp[n - i - 1][2 - sufl][2 - sufp]); sufl = staril, sufp = starip; sufp++; sufl = max(sufl - 1, 0); } //cout << sufl << " " << sufp << endl; } prije = add(prije, 1); cout << prije << "\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...