Submission #99743

#	Time	Username	Problem	Language	Result	Execution time	Memory
99743		nandonathaniel	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	4 ms	568 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL memo[20][11][11][2][2][2];

string s[2];

LL DP(LL digit_ke,LL last1,LL last2,LL flag,LL kata,LL tzero){    
    if(digit_ke>=s[kata].length())return 1;
    if(memo[digit_ke][last1][last2][flag][kata][tzero]!=-1)return memo[digit_ke][last1][last2][flag][kata][tzero];
    LL ans=0;
    if(flag==1){
		if(tzero==1){
			if(s[kata][digit_ke]=='0')ans+=DP(digit_ke+1,10,last1,1,kata,1);
			else ans+=DP(digit_ke+1,(LL)(s[kata][digit_ke]-'0'),last1,1,kata,0);
		}
		else{
			if((LL)(s[kata][digit_ke]-'0')!=last1 && (LL)(s[kata][digit_ke]-'0')!=last2)ans+=DP(digit_ke+1,(LL)(s[kata][digit_ke]-'0'),last1,1,kata,0);
		}
        for(LL dig=0;dig<(LL)(s[kata][digit_ke]-'0');dig++){
			if(tzero==1){
				if(dig==0)ans+=DP(digit_ke+1,10,last1,0,kata,1);
				else ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
			else{
				if(dig!=last1 && dig!=last2)ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
            
        }
    }
    else{
        for(LL dig=0;dig<=9;dig++){
			if(tzero==1){
				if(dig==0)ans+=DP(digit_ke+1,10,last1,0,kata,1);
				else ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
			else{
				if(dig!=last1 && dig!=last2)ans+=DP(digit_ke+1,dig,last1,0,kata,0);
			}
            
        }
    }

    return memo[digit_ke][last1][last2][flag][kata][tzero]=ans;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	memset(memo,-1,sizeof(memo));
	LL L,res2;
	cin >> L >> s[1];
	LL res1=DP(0,10,10,1,1,1);
	if(L==0)res2=0;
	else{
		L--;
		s[0]=to_string(L);
		res2=DP(0,10,10,1,0,1);
	}
	//cout << res1 << " " << res2  << endl;
	cout << res1-res2 << endl;
	return 0;
}

Compilation message (stderr)

numbers.cpp: In function 'LL DP(LL, LL, LL, LL, LL, LL)':
numbers.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(digit_ke>=s[kata].length())return 1;
        ~~~~~~~~^~~~~~~~~~~~~~~~~~

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