oj.uz

Submission #318171

# Submission time Handle Problem Language Result Execution time Memory
318171 2020-10-31T14:42:48 Z Dymo Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 4 ms 4236 KB 
#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 dp[50][20][20][5][5];

ll b[maxn];
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,ll dd)
{


    if (dp[id][nw1][nw2][h][dd]!=-1)
    {
       return dp[id][nw1][nw2][h][dd];
    }
     if (id==cnt1) return dp[id][nw1][nw2][h][dd]=1;
    ll t=0;
    if (dd==0)
    {
        t=t+dosth(id+1,10,10,1,0);
    }
    for (int i=0;i<=9;i++)
    {
        if (dd==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),1);
    }
    return dp[id][nw1][nw2][h][dd]=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,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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4204 KB Output is correct
4 Correct 2 ms 4204 KB Output is correct
5 Correct 3 ms 4204 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 3 ms 4204 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Correct 3 ms 4204 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 3 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 3 ms 4204 KB Output is correct
14 Correct 2 ms 4204 KB Output is correct
15 Correct 3 ms 4204 KB Output is correct
16 Correct 3 ms 4204 KB Output is correct
17 Correct 4 ms 4204 KB Output is correct
18 Correct 2 ms 4204 KB Output is correct
19 Correct 3 ms 4204 KB Output is correct
20 Correct 3 ms 4204 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 ms 4204 KB Output is correct
3 Correct 3 ms 4204 KB Output is correct
4 Correct 3 ms 4204 KB Output is correct
5 Correct 3 ms 4204 KB Output is correct
6 Correct 4 ms 4204 KB Output is correct
7 Correct 3 ms 4204 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Correct 3 ms 4204 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 4 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 3 ms 4204 KB Output is correct
14 Correct 3 ms 4204 KB Output is correct
15 Correct 3 ms 4204 KB Output is correct
16 Correct 3 ms 4204 KB Output is correct
17 Correct 3 ms 4204 KB Output is correct
18 Correct 3 ms 4204 KB Output is correct
19 Correct 3 ms 4204 KB Output is correct
20 Correct 3 ms 4204 KB Output is correct
21 Correct 3 ms 4204 KB Output is correct
22 Correct 3 ms 4204 KB Output is correct
23 Correct 3 ms 4204 KB Output is correct
24 Correct 3 ms 4204 KB Output is correct
25 Correct 3 ms 4204 KB Output is correct
26 Correct 3 ms 4236 KB Output is correct
27 Correct 3 ms 4204 KB Output is correct
28 Correct 3 ms 4204 KB Output is correct
29 Correct 3 ms 4204 KB Output is correct
30 Correct 3 ms 4204 KB Output is correct
31 Correct 3 ms 4204 KB Output is correct
32 Correct 3 ms 4204 KB Output is correct
33 Correct 3 ms 4204 KB Output is correct
34 Correct 4 ms 4204 KB Output is correct
35 Correct 4 ms 4204 KB Output is correct
36 Correct 3 ms 4204 KB Output is correct
37 Correct 3 ms 4204 KB Output is correct
38 Correct 3 ms 4204 KB Output is correct
39 Correct 3 ms 4204 KB Output is correct
40 Correct 3 ms 4204 KB Output is correct
41 Correct 3 ms 4204 KB Output is correct
42 Correct 3 ms 4204 KB Output is correct
43 Correct 3 ms 4204 KB Output is correct
44 Correct 3 ms 4204 KB Output is correct
45 Correct 3 ms 4204 KB Output is correct