Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class Main {
- static long mod = 1000000000+7;
- static int n1;
- static int n2;
- static int noOfStudent;
- public static long optimized(int i , int g, int boysPlaced, int girlsPlaced, long[][][][] dp){
- if(i == noOfStudent+1){
- return 1;
- }
- long ways = 0;
- if(dp[i][g][boysPlaced][girlsPlaced] != -1){
- return dp[i][g][boysPlaced][girlsPlaced];
- }
- int b = noOfStudent - (i-1);
- b = b-g;
- // place a boy
- if(b > 0 && boysPlaced < n1){
- ways += optimized(i+1,g,boysPlaced+1,0,dp)%mod;
- }
- // place a girl
- if(g > 0 && girlsPlaced < n2){
- ways += optimized(i+1,g-1,0,girlsPlaced+1,dp)%mod;
- }
- return dp[i][g][boysPlaced][girlsPlaced] = ways;
- }
- public static void main(String args[]) throws Exception {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- String[] in = br.readLine().trim().split(" ");
- int b = Integer.parseInt(in[0]);
- int g = Integer.parseInt(in[1]);
- n1 = Integer.parseInt(in[2]);
- n2 = Integer.parseInt(in[3]);
- noOfStudent = b+g;
- long[][][][] dp = new long[noOfStudent+1][g+1][21][21];
- for(int i = 0; i < dp.length; i++){
- for(int j = 0; j < dp[i].length; j++){
- for(int k = 0; k < dp[i][j].length; k++){
- Arrays.fill(dp[i][j][k],-1);
- }
- }
- }
- System.out.println(optimized(1,g,0,0,dp));
- }
- }
Add Comment
Please, Sign In to add comment