➤ Problem Link : ANARC05H
👉 Hint : Simple 2D DP
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll dp[26][226];
int main()
{
string s;
ll k=0;
while(1)
{
ll val=0,sum=0;
cin>>s;
if(s=="bye")
break;
ll n=s.length();
memset(dp,0,sizeof(dp));
for(ll i=0;i<n;i++)
{
val+=s[i]-'0';
dp[i][val]=1;
}
for(ll i=1;i<n;i++)
{
val=0;
for(ll j=i;j>0;j--)
{
val+=s[j]-'0';
for(ll k=0;k<=val;k++)
dp[i][val]+=dp[j-1][k];
}
}
for(ll i=0;i<=225;i++)
sum+=dp[n-1][i];
cout<<++k<<". "<<sum<<endl;
}
}
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.