Submission #203424

#	Time	Username	Problem	Language	Result	Execution time	Memory
203424		mdn2002	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	7 ms	1656 KiB

numbers

#include<bits/stdc++.h>
using namespace std;
string a,b;
long long dp[25][15][15][3][3][3];
long long f(int x,int last,int llast,int on,int of,int tk)
{
    if(x==b.size())return 1;
    if(dp[x][last][llast][on][of][tk]!=-1)return dp[x][last][llast][on][of][tk];
    long long ans=0;
    for(int i=0;i<=9;i++)
    {
        int oon=on,oof=of,tkk=tk;
        if(i)tkk=1;
        char dj='0'+i;
        if(a[x]<dj)oon=0;
        if(dj<b[x])oof=0;
        if(on&&a[x]>dj)continue;
        if(of&&dj>b[x])continue;
        if(tk)
        {
            if(last==i||llast==i)continue;
        }
        if(tkk==0)ans+=f(x+1,10,10,oon,oof,tkk);
        else ans+=f(x+1,i,last,oon,oof,tkk);
    }
    return dp[x][last][llast][on][of][tk]=ans;
}
int main()
{
    memset(dp,-1,sizeof dp);
    cin>>a>>b;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    while(a.size()!=20)a.push_back('0');
    while(b.size()!=20)b.push_back('0');
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    cout<<f(0,10,10,1,1,0);
}

Compilation message (stderr)

numbers.cpp: In function 'long long int f(int, int, int, int, int, int)':
numbers.cpp:7:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(x==b.size())return 1;
        ~^~~~~~~~~~

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