R24D

Round 24D

#include<bits/stdc++.h>
#define int int
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
int dp[20][10][2], num[20], len;
int dist[20][20] = {
	{0, 4, 3, 3, 4, 4, 2, 3, 1, 2}, 
	{4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
	{3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
	{3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
	{4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
	{3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
	{2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
	{3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
	{1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
	{2, 4, 3, 1, 2, 1, 2, 3, 1, 0},
};
int calc(int a) {
	int ans = 0;
	for(int i = 1; i <= a; i++)ans += dist[i][i - 1];
	return ans;
}
int dfs(int x, int lst, bool flag, bool zero) {
	if (x == len + 1) return 0;
	if (!flag && dp[x][lst][zero] != -1) return dp[x][lst][zero];
	int mid = flag ? num[x] : 9, ans = 0;
	for (int d = 0; d <= mid; d++) {
		bool nx = flag && (d == mid), nz = (zero && (d == 0));
		if (nz) {
			ans += dfs(x + 1, 0, nx, nz);
		} else {
			int tot = calc(d) + lst * 28;
			ans += tot + dfs(x + 1, lst * 10 + d, nx, 0);
		}
	}
	if (!flag) dp[x][lst][zero] = ans;
	return ans;
}
int solve(int n) {
	if (n <= 0) return 0;
	len = 0;
	while (n) {
		num[++len] = n % 10;
		n /= 10;
	}
	for(int i = 1, j = len; i < j; i++, j--) swap(num[i], num[j]);
	memset(dp, -1, sizeof(dp));	
	return dfs(1, 0, 1, 1);
}
int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int l, r;
	cin >> l >> r;
	cout << solve(r) - solve(l - 1) << '\n';
	return 0;
}