Codeforces, Contest 1036: C. Classy Numbers (Digit Dynamic Programming)

#include<bits/stdc++.h>

#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define Bye return 0
#define CodeTyper main
#define ll int long long

using namespace std;

ll dp[20][2][10];

ll digit_dp(int pos, int flag, int sum, string str){
    if(sum > 3)
        return 0;

    if(pos == str.size())
        return 1;

    if(dp[pos][flag][sum] != -1)
        return dp[pos][flag][sum];

    ll res = 0;
    int end = flag ? str[pos] - '0' : 9;
    for (int j = 0; j <= end; j++){
        int new_flag = (j == str[pos] - '0') ? flag : 0;
        res += digit_dp(pos + 1, new_flag, sum + (j != 0), str);
    }

    return dp[pos][flag][sum] = res;
}

void reset_dp(){
    memset(dp, -1, sizeof dp);
}

void solve() {
    ll a, b; cin>>a>>b; a--;
    string str_b = to_string(b);
    string str_a = to_string(a);

    reset_dp();
    ll r = digit_dp(0, 1, 0, str_b);
    reset_dp();
    ll l = digit_dp(0, 1, 0, str_a);

    l = a < 0 ? 0 : l;

    cout<<(r - l)<<endl;
}

int CodeTyper()
{
    boost;
    int t; cin>>t;
    while(t--)
        solve();
    Bye;
}

/*
    'Think FIRST, then CODE.'
    'May the CODE be with YOU.'
*/