Submission #939032

#	Time	Username	Problem	Language	Result	Execution time	Memory
939032		tamir1	Palindrome-Free Numbers (BOI13_numbers)	C++17	100 / 100	1 ms	804 KiB

numbers

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,dp[20][180][2][2][2];
vector<ll> v;
void build(ll a){
	if(a<10){
		v.push_back(a);
		return;
	}
	build(a/10);
	v.push_back(a%10);
}
ll rec(ll idx,ll sum,ll t,ll s,ll u,ll last1,ll last2){
	if(idx==v.size()) return 1;
	if(dp[idx][sum][t][s][u]!=-1) return dp[idx][sum][t][s][u];
	ll i,up=9,ans=0;
	if(!t) up=v[idx];
	for(i=0;i<=up;i++){
		if(s && last2==i) continue;
		if(u && last1==i) continue;
		ans+=rec(idx+1,sum+i,t|(i<up),s|(i>0),u|s,last2,i);
	}
	return dp[idx][sum][t][s][u]=ans;
}
ll solve(ll a){
	if(a==-1) return 0;
	v.clear();
	build(a);
	memset(dp,-1,sizeof dp);
	return rec(0,0,0,0,0,0,0);
}
int main(){
	cin >> a >> b;
	cout << solve(b)-solve(a-1);
}

Compilation message (stderr)

numbers.cpp: In function 'long long int rec(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
numbers.cpp:15:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(idx==v.size()) return 1;
      |     ~~~^~~~~~~~~~

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