Submission #1008634

#TimeUsernameProblemLanguageResultExecution timeMemory
1008634vqpahmadLinear Garden (IOI08_linear_garden)C++17
0 / 100
86 ms65540 KiB
#include<bits/stdc++.h> using namespace std; #ifdef ONPC #include"debug.h" #else #define debug(...) 42 #endif #define endl '\n' #define ll long long #define pii pair<int,int> #define F first #define S second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() #define int long long template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } int mod = 1e9 + 7; const int MAXN = 1e6 + 15; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; int n; int dp[MAXN][5][5][5]; // len, min ,max, cur int calc(int len, int mn, int mx, int cur){ if (mx - mn > 2 || cur < 0) return 0; if (dp[len][mn][mx][cur] != -1) return dp[len][mn][mx][cur]; if (len == 0) return dp[len][mn][mx][cur] = 1; return dp[len][mn][mx][cur] = (calc(len - 1, min(mn, cur - 1), mx, cur - 1) + calc(len - 1, mn, max(mx, cur + 1), cur + 1))%mod; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); memset(dp, -1, sizeof(dp)); cin >> n >> mod; string s; cin >> s; int cur_sum = 2, mn = 2, mx = 2; int ans = 1; for (int i = 0; i < n; i++){ if (s[i] == 'L'){ cur_sum--; ckmin(mn, cur_sum); continue; } // now it is P cur_sum--; ans += calc(n - i - 1, min(cur_sum, mn), mx, cur_sum); ans %= mod; cur_sum += 2; ckmax(mx, cur_sum); } cout << ans << endl; }
#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...