CF:Gym problem-G ( Digit DP )

CF:Gym problem-G ( Digit DP )

Accoring to problem, You have given interval L,R.
You have to print number which have  maximum product of the digits.
Idea:
    Digit DP storing state of
    1.Position-p
    2.flag for did I take small(chhoto)-ch
    3.flag for did I take large(boro)-br
    4.flag for statting of nonzero val-z

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     200005
#define inf    2000000010
#define MD     1000000007
#define eps    1e-9
///===============================///

char a[20],b[20];
ll n,dp[20][2][2][2];

ll go(int p,int ch,int br,int z){
    if( p==n ) {
        if(!z) return 0LL;
        return 1LL;
    }
    ll &ret=dp[p][ch][br][z];
    if(ret!=-1) return ret;
    ret=0LL;
    int mx=b[ p ]-'0';
    if(ch)mx=9;
    int mn=a[ p ]-'0';
    if(br)mn=0;
    for(ll i=mn;i<=mx;i++){
        ll mul=1LL;
        int nz=(z||i>0);
        if(nz)mul=i;
        ret=max( ret,mul*go(p+1,ch||i<mx,br||i>mn,nz) );
    }
    return ret;
}

ll go2(int p,int ch,int br,int z){
    if( p==n ) {
        if(!z) return 0LL;
        return 1LL;
    }
    ll &ret=dp[p][ch][br][z];

    int mx=b[ p ]-'0';
    if(ch)mx=9;
    int mn=a[ p ]-'0';
    if(br)mn=0;
    for(ll i=mn;i<=mx;i++){
        ll mul=1LL;
        int nz=(z||i>0);
        if(nz)mul=i;
        if( ret==mul*go(p+1,ch||i<mx,br||i>mn,nz) ){
            if(nz)printf("%d",i);
            go2(p+1,ch||i<mx,br||i>mn,nz);
            break;
        }
    }
    return ret;
}

int main(){
    ll l,r;
    SL2(l,r);
    SET(dp);
    sprintf(a,"%019lld",l); ///Converting to 19 digit string adding LeadingZero
    sprintf(b,"%019lld",r);

    n=19;
    ll ans=go(0,0,0,0);

    go2(0,0,0,0);
    printf("\n");

    return 0;
}