Submission #1172883

#TimeUsernameProblemLanguageResultExecution timeMemory
1172883Dan4LifeLinear Garden (IOI08_linear_garden)C++20
75 / 100
158 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) begin(a),end(a) using ll = long long; using ar2 = array<ll,2>; using vi = vector<int>; const int mxN = (int)1e6+10; const ll INF = (int)1e9; int n, MOD; string s; int dp[mxN][3][2][2]; int recur(int pos, int t, int lst, bool row, bool sm=0){ if(pos==n) return 1; int &res = dp[pos][t][lst][row]; if(sm and res!=-1) return res; int lim = sm?1:s[pos], ans = 0; for(int d = 0; d <= lim; d++){ if((t==d or row) and d==lst) continue; ans+=recur(pos+1,lst==d?d:t,d,d==lst, sm|(d<lim)); if(ans>=MOD)ans-=MOD; } return sm?res=ans:ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> MOD >> s; memset(dp,-1,sizeof(dp)); for(auto &u:s)u=(u=='L'?0:1); cout << recur(0,2,2,0) << "\n"; }
#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...