Submission #1285324

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

numbers

//~ #pragma GCC optimize("O3,unroll-loops")
//~ #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define int long long
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

const int inf  = INT_MAX;
const int mod  = 1e9+7;

string a, b;
int ind;
int dp[20][11][11][3]; //ind, onceki rakam, iki onceki rakam, min/maks sinir, palindrom yok/var

int32_t main(){
	cin>>a>>b;
	while(a.size()<=18){
		a = ':' + a; // ':' - '0' = 10
	}
	while(b.size()<=18){
		b = ':' + b;
	}
	for(int i=0;i<=18;i++){
		if(a[i] == b[i])ind++;
		else break;
	}
	//~ cerr<<a<<"   "<<b<<endl;
	//~ cerr<<st1<<" .. "<<st2<<" .. "<<ind<<endl;
	dp[0][a[0]-'0'][0][0] = 1;
	dp[0][b[0]-'0'][0][1] = 1;
	for(int i=0;i<=9;i++){
		if(i<=a[0]-'0' || i>=b[0]-'0')continue;
		dp[0][i][0][2] = 1;
	}
	for(int i=1;i<=18;i++){
		dp[i][10][10][2] += dp[i-1][10][10][2];
		for(int x=0;x<=10;x++){
			for(int y=0;y<=10;y++){
				if(x!=10 && x==y)continue;
				if(x==0 && y==10)continue;
				for(int z=0;z<=10;z++){
					if(x!=10 && z==x)continue;
					if(x!=10)dp[i][x][y][2] += dp[i-1][y][z][2];
					//~ cout<<i<<" .. "<<x<<" .. "<<y<<" .. "<<z<<" .. "<<dp[i][x][y][z]<<endl;
					if(x==a[i]-'0'){
						dp[i][x][y][0] += dp[i-1][y][z][0];
					}
					else if(x > (a[i]-'0')%10 && !(i<=ind && x >= (b[i] - '0')%10)){
						if(x!=10)dp[i][x][y][2] += dp[i-1][y][z][0];
					}
					if(x==b[i]-'0'){
						dp[i][x][y][1] += dp[i-1][y][z][1]; 
					}
					else if(x < (b[i]-'0')%10 && i > ind){
						if(x!=10)dp[i][x][y][2] += dp[i-1][y][z][1]; 
					}
				}
				//~ if(dp[i][x][y][0])cerr<<dp[i][x][y][0]<<" .. "<<i<<" .. "<<x<<" .. "<<y<<" .. "<<0<<endl;
				//~ if(dp[i][x][y][1])cerr<<dp[i][x][y][1]<<" .. "<<i<<" .. "<<x<<" .. "<<y<<" .. "<<1<<endl;
				//~ if(dp[i][x][y][2])cerr<<dp[i][x][y][2]<<" .. "<<i<<" .. "<<x<<" .. "<<y<<" .. "<<2<<endl;
			}
		}
	}
	int ans = 0;
	for(int x=0;x<=9;x++){
		for(int y=0;y<=10;y++){
			ans += dp[18][x][y][0];
			if(a!=b)ans += dp[18][x][y][1];
			ans += dp[18][x][y][2];
		}
	}
	if(a.back() == '0')ans++;
	cout<<ans<<endl;
	
}







//https://usaco.org/current/current/index.php?page=viewproblem2&cpid=282 bunu coz

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