제출 #1288551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288551		Jawad_Akbar_JJ	Palindrome-Free Numbers (BOI13_numbers)	C++20	72.50 / 100	2 ms	604 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)
						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];
				}
			}
		}
	}

	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: 12.5 / 25
• Subtask 2: 60 / 75