Submission #1288555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288555		Jawad_Akbar_JJ	Palindrome-Free Numbers (BOI13_numbers)	C++20	100 / 100	2 ms	588 KiB

numbers

#include <iostream>

using namespace std;
#define int long long
int dp[30][30][30][2];

int get(int x, int Ans = 0){
	if (x < 10)
		return x + 1;
	string s = to_string(x);

	for (int i=0;i<=20;i++){
		for (int j=0;j<=11;j++)
			for (int k=0;k<=11;k++)
				for (int l : {0, 1})
					dp[i][j][k][l] = 0;
	}

	dp[0][11][11][1] = 1;
	int n = s.size();
	for (int i=1;i<=n;i++){
		int cur = s[i-1] - '0';
		for (int j=0;j<=11;j++){
			for (int k=0;k<=11;k++){
				for (int d=0;d<10;d++){
					if (d == j or d == k or (j + k == 22 and d == 0))
						continue;
					dp[i][k][d][0] += dp[i-1][j][k][0];

					if (d == cur)
						dp[i][k][d][1] += dp[i-1][j][k][1];
					if (d < cur)
						dp[i][k][d][0] += dp[i-1][j][k][1];
				}
			}
		}
		dp[i][11][11][0] = 1;
	}

	for (int j=0;j<=11;j++){
		for (int k=0;k<=11;k++)
			for (int l : {0, 1})
				Ans += dp[n][j][k][l];
	}
	return Ans;
}

signed main(){
	int a, b;
	cin>>a>>b;

	cout<<get(b) - get(a - 1)<<endl;
}

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75