➤ Problem Link : 118D. Caesar's Legions
✅ C++ Solution :
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define m 100000000
int main()
{
int n1,n2,k1,k2;
cin>>n1>>n2>>k1>>k2;
ll dp[n1+n2+1][n1+1][2];
dp[0][0][0]=dp[0][0][1]=1;
for(int i=1;i<=n1;i++)
dp[0][i][0]=dp[0][i][1]=0;
for(int i=1;i<=n1+n2;i++)
{
for(int j=0;j<=n1 && j<=i;j++)
{
dp[i][j][0]=dp[i][j][1]=0;
for(int k=1;k<=k1 && k<=j && i-k>=0;k++)
dp[i][j][0]=(dp[i][j][0]+dp[i-k][j-k][1])%m;
for(int k=1;k<=k2 && k<=(i-j) && i-k>=0;k++)
dp[i][j][1]=(dp[i][j][1]+dp[i-k][j][0])%m;
}
}
cout<<(dp[n1+n2][n1][0]+dp[n1+n2][n1][1])%m;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.