12 months ago

suryansh jaiswal • 370

Lucknow

Question 1 solution 

vector<vector<int>> dp;
int dfs(vector<vector<int>>& e, int i, int k) {
    if (k == 0 || i >= e.size())
        return 0;
    if (dp[i][k] != -1) 
        return dp[i][k];
    auto j = upper_bound(begin(e) + i, end(e), e[i][1], 
        [](int t, const vector<int> &v) {return v[0] > t;}) - begin(e);
    return dp[i][k] = max(e[i][2] + dfs(e, j, k - 1), dfs(e, i + 1, k));
}
int maxValue(vector<vector<int>>& events, int k) {
    dp = vector<vector<int>>(events.size(), vector<int>(k + 1, -1));
    sort(begin(events), end(events));
    return dfs(events, 0, k);
}

12 months ago

suryansh jaiswal • 370

Lucknow

Question 2 solution

int dp[25][2][2][2][12];
int sol(int i,string &s,bool adj,int lim,bool flag,int prev)
{
   // cout<<i<<endl;
    int n=s.size();
    if(i>=n)
    {
        return (flag)&(!adj);
    }
    if(dp[i][adj][lim][flag][prev+1]!=-1)
        return dp[i][adj][lim][flag][prev+1];
    int res=0;
    int depth=lim?(s[i]-'0'):9;
    for(int j=0;j<=depth;j++)
    {
        int newlimit;
        bool newflag;
        bool newadj;
        if(j==depth && lim)
            newlimit=1;
        else
            newlimit=0;
        if(j!=0 || flag)
            newflag=1;
        else
            newflag=0;
        if(prev==j || adj)
            newadj=1;
        else
            newadj=0;
        res+=sol(i+1,s,newadj,newlimit,newflag,j);
    }
    return dp[i][adj][lim][flag][prev+1]=res;
}
void solve()
{
memset(dp,-1,sizeof(dp));
int a,b;
cin>>a>>b;
a--;
string x=to_string(a);
int ans1=sol(0,x,0,1,0,-1);
memset(dp,-1,sizeof(dp));
string y=to_string(b);
int ans2=sol(0,y,0,1,0,-1);
cout<<ans2-ans1<<endl;
}