fork(2) download
  1. #include <bits/stdc++.h>
  2. #define lli long long int
  3. #define li long int
  4. #define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. #define nl "\n"
  6. #define ff first
  7. #define ss second
  8. #define pb push_back
  9. #define mp make_pair
  10. using namespace std;
  11.  
  12. li dp[2000][2000];
  13.  
  14. li sleepingRecursive(li arr[], li n, li h, li l, li r, li s, li i)
  15. {
  16. if(i >= n)
  17. return (s>=l && s<=r);
  18. if(dp[i][s] != -1)
  19. return dp[i][s];
  20. if(s>=l && s<=r)
  21. dp[i][s] = 1+max(sleepingRecursive(arr,n,h,l,r,(s+arr[i])%h,i+1),sleepingRecursive(arr,n,h,l,r,(s+arr[i]-1)%h,i+1));
  22. else
  23. dp[i][s] = max(sleepingRecursive(arr,n,h,l,r,(s+arr[i])%h,i+1),sleepingRecursive(arr,n,h,l,r,(s+arr[i]-1)%h,i+1));
  24. return dp[i][s];
  25. }
  26.  
  27. int main()
  28. {
  29. li n,h,l,r,i,j;
  30. cin>>n>>h>>l>>r;
  31. li arr[n];
  32. for(i=0;i<n;i++)
  33. cin>>arr[i];
  34. for(i=0;i<n;i++)
  35. for(j=0;j<h;j++)
  36. dp[i][j] = -1;
  37. cout<<max(sleepingRecursive(arr,n,h,l,r,arr[0],1),sleepingRecursive(arr,n,h,l,r,arr[0]-1,1));
  38. }
Success #stdin #stdout 0s 4380KB
stdin
7 24 21 23
16 17 14 20 20 11 22
stdout
3