제출 #1126003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126003		Muhammet	Palindrome-Free Numbers (BOI13_numbers)	C++20	66.67 / 100	1 ms	328 KiB

numbers

#include <bits/stdc++.h>

using namespace std;

#define SZ(s) (int)s.size()
#define ll long long

ll p[20], dp[20][2][10][10][3];

ll f1(int pos, bool big, int last_dig, int pre_last_dig, int ds){
	if(pos == 19) return 1;
	int ans = dp[pos][big][last_dig][pre_last_dig][ds];
	if(ans != -1) return ans;
	ans = 0;
	for(int d = 0; d < 10; d++){
		if(big == false and d > p[pos]) continue;
		if(ds >= 1 and d == last_dig) continue;
		if(ds == 2 and d == pre_last_dig) continue;
		bool new_big = (big or (d < p[pos]));
		int new_ds = 2;
		if(ds == 0 and d == 0) new_ds = 0;
		else if(ds == 0 and d) new_ds = 1;
		ans += f1(pos+1, new_big, d, last_dig, new_ds);
	}
	return dp[pos][big][last_dig][pre_last_dig][ds] = ans;
}

ll f(ll x){
	if(x < 0) return 0;
	for(int i1 = 0; i1 < 20; i1++){
		for(int i2 = 0; i2 < 2; i2++){
			for(int i3 = 0; i3 < 10; i3++){
				for(int i4 = 0; i4 < 10; i4++){
					for(int i5 = 0; i5 < 3; i5++){
						dp[i1][i2][i3][i4][i5] = -1;
					}
				}
			}
		}
	}
	for(int i = 18; i >= 0; i--){
		p[i] = (x % 10); x /= 10;
	}
	return f1(0,0,0,0,0);
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	ll a, b;
	cin >> a >> b;
	// cout << f(1) << ' ' << f(a) << ' ' << f(b) << '\n';
	cout <<  (f(b)-f(a-1));
}

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