제출 #1289162

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

numbers

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
int mem[20][11][11][2];
string num;

int dp(int x, int p2, int p1, bool ib){
	if(mem[x][p2][p1][ib] != -1)return mem[x][p2][p1][ib];
	if(x >= num.size())return 1;
	int cdig=num[x]-'0', sm=0;
	if(ib){
		if(p1 == 10){
			assert(p2==10);
			sm += dp(x+1, 10, 10, 0);
		}
		else if (p1 != 0 and p2 != 0){
			sm += dp(x+1, p1, 0, (cdig==0));
		}
		for(int i=1;i<cdig;i++){
			if(i != p2 and i != p1){
				sm+=dp(x+1, p1, i, 0);
			}
		}
		if (p1 != cdig and p2 != cdig and cdig != 0){
			sm+=dp(x+1, p1, cdig, 1);
		}
	}
	else{
		if (p1 == 10){
			assert(p2==10);
			sm += dp(x+1, 10, 10, 0);
		}
		else{
			if(p1 != 0 and p2 != 0) sm+=dp(x+1, p1, 0, 0);
		}
		for(int i=1;i<10;i++){
			if(p1 != i and p2 != i) sm+=dp(x+1, p1, i, 0);
		}
	}
	return mem[x][p2][p1][ib]=sm;
}
signed main(){
	int bel, abv, temp;
	cin>>temp;
	memset(mem, -1, sizeof mem);
	if(temp==0){
		bel=0;
	}
	else {
		num=to_string(temp-1);
		bel=dp(0, 10, 10, 1);
	}
	memset(mem, -1, sizeof mem);
	cin>>num;
	abv=dp(0, 10, 10, 1);
	//printf("bel %lld, abv %lld\n", bel, abv);
	cout<<abv-bel;
}

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