Advertisement
Saleh127

CSES 1746 / DP

Aug 9th, 2022
517
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. /***
  2.  created: 2022-08-09-21.49.04
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10. template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
  11. #define ll long long
  12. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  13. #define get_lost_idiot return 0
  14. #define nl '\n'
  15.  
  16.  
  17. ll dp[100005][105];
  18. ll a[100005],n,m,mod=1e9+7;
  19.  
  20. ll solve(ll in,ll val)
  21. {
  22.     if(val<1 || val>m) return 0;
  23.  
  24.     if(a[in] && a[in]!=val) return 0;
  25.  
  26.     if(dp[in][val]!=-1) return dp[in][val];
  27.  
  28.     if(in==n) return 1;
  29.  
  30.     ll ans=((solve(in+1,val+1)%mod + solve(in+1,val-1)%mod)%mod+ solve(in+1,val)%mod)%mod;
  31.  
  32.     return dp[in][val]=ans;
  33. }
  34.  
  35.  
  36. int main()
  37. {
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cout.tie(0);
  41.  
  42.     cin>>n>>m;
  43.  
  44.     for(ll i=1; i<=n; i++)
  45.     {
  46.         cin>>a[i];
  47.     }
  48.  
  49.     memset(dp,-1,sizeof dp);
  50.  
  51.     ll ans=0;
  52.  
  53.     for(ll i=1;i<=m;i++)
  54.     {
  55.         ans+=solve(1,i);
  56.         ans%=mod;
  57.     }
  58.  
  59.     cout<<ans<<nl;
  60.  
  61.     get_lost_idiot;
  62. }
  63.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement