Submission #78386

#	Time	Username	Problem	Language	Result	Execution time	Memory
78386		HellAngel	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	3 ms	804 KiB

numbers

#include <bits/stdc++.h>
#define int long long

using namespace std;
string s;
int a, b;

int dp[21][2][2][11][11];

string Convert(int a)
{
    string s = "";
    if(a == 0) return "0";
    while(a > 0)
    {
        s += a % 10 + '0';
        a /= 10;
    }
    reverse(s.begin(), s.end());
    return s;
}

int DP(int pos, bool prefix, bool allz, int last1, int last2)
{
    //cout << pos << ' ' << prefix << ' ' << allz << ' ' << last1 << ' ' << last2 << '\n';
    if(~dp[pos][prefix][allz][last1][last2]) return dp[pos][prefix][allz][last1][last2];
    if(pos == s.length()) return 1;
    int limit;
    if(prefix) limit = s[pos] - '0';
    else limit = 9;
    int ans = 0;
    for(int d = 0; d <= limit; d++)
    {
        int digit;
        if(d == 0 && allz) digit = 10;
        else digit = d;
        if(digit != 10 && digit == last1) continue;
        if(digit != 10 && digit == last2) continue;
        ans += DP(pos + 1, prefix && d == limit, allz && d == 0, last2, digit);
    }
    return dp[pos][prefix][allz][last1][last2] = ans;
}

int Get()
{
    fill_n(&dp[0][0][0][0][0], 21 * 2 * 2 * 11 * 11, -1);
    return DP(0, 1, 1, 10, 10);
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> a >> b;
    s = Convert(a - 1);
    int ans1 = Get();
    s = Convert(b);
    int ans2 = Get();
    if(a == 0) ans2++;
    cout << ans2 - ans1;
}

Compilation message (stderr)

numbers.cpp: In function 'long long int DP(long long int, bool, bool, long long int, long long int)':
numbers.cpp:27:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos == s.length()) return 1;
        ~~~~^~~~~~~~~~~~~

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