Guest User

code

a guest
Jul 14th, 2020
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.88 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Main {
  5. static long mod = 1000000000+7;
  6. static int n1;
  7. static int n2;
  8. static int noOfStudent;
  9.  
  10.  
  11.  
  12. public static long optimized(int i , int g, int boysPlaced, int girlsPlaced, long[][][][] dp){
  13. if(i == noOfStudent+1){
  14. return 1;
  15. }
  16.  
  17. long ways = 0;
  18. if(dp[i][g][boysPlaced][girlsPlaced] != -1){
  19. return dp[i][g][boysPlaced][girlsPlaced];
  20. }
  21.  
  22. int b = noOfStudent - (i-1);
  23. b = b-g;
  24.  
  25.  
  26.  
  27. // place a boy
  28. if(b > 0 && boysPlaced < n1){
  29. ways += optimized(i+1,g,boysPlaced+1,0,dp)%mod;
  30. }
  31.  
  32.  
  33.  
  34. // place a girl
  35. if(g > 0 && girlsPlaced < n2){
  36. ways += optimized(i+1,g-1,0,girlsPlaced+1,dp)%mod;
  37. }
  38.  
  39.  
  40. return dp[i][g][boysPlaced][girlsPlaced] = ways;
  41.  
  42.  
  43. }
  44.  
  45.  
  46.  
  47. public static void main(String args[]) throws Exception {
  48. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  49. String[] in = br.readLine().trim().split(" ");
  50.  
  51. int b = Integer.parseInt(in[0]);
  52. int g = Integer.parseInt(in[1]);
  53.  
  54. n1 = Integer.parseInt(in[2]);
  55. n2 = Integer.parseInt(in[3]);
  56. noOfStudent = b+g;
  57.  
  58. long[][][][] dp = new long[noOfStudent+1][g+1][21][21];
  59.  
  60.  
  61.  
  62. for(int i = 0; i < dp.length; i++){
  63. for(int j = 0; j < dp[i].length; j++){
  64. for(int k = 0; k < dp[i][j].length; k++){
  65. Arrays.fill(dp[i][j][k],-1);
  66. }
  67. }
  68. }
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75. System.out.println(optimized(1,g,0,0,dp));
  76.  
  77. }
  78. }
Add Comment
Please, Sign In to add comment