Guest User

Untitled

a guest
Apr 24th, 2019
50
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. // Created by Naman Bhalla on 2019-04-14.
  3. //
  4.  
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <iostream>
  10. #include <utility>
  11.  
  12. using namespace std;
  13.  
  14. const int mod{100000000};
  15. int dp[101][101][2]; // 0 -> Foot 1 -> Horse
  16. int main(){
  17. int n1, n2, k1, k2;
  18. memset(dp, 0, sizeof dp);
  19. cin >> n1 >> n2 >> k1 >> k2;
  20. dp[0][0][0] = 1;
  21. dp[0][0][1] = 1;
  22.  
  23. for(int i{0} ; i <= n1; ++i){
  24. for(int j{0}; j <= n2; ++j){
  25. for(int k{0}; k <= 1; ++k){
  26. if(i == 0 and j == 0){
  27. dp[i][j][k] = 1;
  28. } else {
  29. if(k){
  30. for(int tgthr{1}; tgthr <= min(j, k2); ++tgthr){
  31. dp[i][j][k] += dp[i][j - tgthr][0];
  32. dp[i][j][k] %= mod;
  33. }
  34. } else {
  35. for(int tgthr{1}; tgthr <= min(i, k1); ++tgthr){
  36. dp[i][j][k] += dp[i - tgthr][j][1];
  37. dp[i][j][k] %= mod;
  38. }
  39. }
  40. }
  41. }
  42. }
  43. }
  44.  
  45. cout << ((dp[n1][n2][0] % mod) + (dp[n1][n2][1] % mod)) % mod << endl;
  46.  
  47.  
  48. return 0;
  49. }
RAW Paste Data