Submission #318163

#	Time	Username	Problem	Language	Result	Execution time	Memory
318163		Dymo	Palindrome-Free Numbers (BOI13_numbers)	C++14	73.75 / 100	26 ms	39660 KiB

numbers

#include<bits/stdc++.h>

using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
//#define endl "\n"
const ll maxn=1e6+50;
const ll mod =998244353 ;
const ll base=3e18;
ll b[100];
ll dp[100][100][100][5];
ll dp1[100][100][100][5];

ll cnt1;
ll dem(ll p)
{
   ll cnt=0;
   while (p)
   {
       cnt++;
       p/=10;
   }
   return cnt;
}
ll dem1=0;
ll dosth(ll id,ll nw1,ll nw2,ll h)
{


    if (dp[id][nw1][nw2][h]!=-1)
    {
       return dp[id][nw1][nw2][h];
    }
     if (id==cnt1) return dp[id][nw1][nw2][h]=1;
    ll t=0;
    if (id==0)
    {
        t=t+dosth(id+1,10,10,1);
    }
    for (int i=0;i<=9;i++)
    {
        if (id==0&&i==0) continue;
        if (!h&&b[id+1]<i) continue;
        if (i==nw1||i==nw2) continue;
        t=t+dosth(id+1,nw2,i,h|(b[id+1]>i));
    }
    dem1++;
   // dp1[id][nw1][nw2][h]++;

   // cout <<id<<" "<<nw1<<" "<<nw2<<" "<<h<<" "<<dem1<<" "<<dp1[id][nw1][nw2][h]<<endl;
    return dp[id][nw1][nw2][h]=t;


}
ll cntpp(ll a)
{
    if (a<0) return 0;

    cnt1 =dem(a);
    ll h= cnt1;
    memset(dp,-1,sizeof(dp));
    while (a)
    {
        b[h]=(a%10);
        a/=10;
        h--;
    }

    /*for (int i=1;i<=cnt1;i++)
    {
        cout <<b[i]<<endl;
    }*/
    return dosth(0,10,10,0);

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*if (fopen("p.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }*/
    ll a, b;
    cin>> a>> b;
     cout <<cntpp(b)-cntpp(a-1);
    //  cout <<cntpp(a)<<endl;





}

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