Submission #78386

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
78386	2018-10-04T15:01:16 Z	HellAngel	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	3 ms	804 KB

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

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.0 / 25.0

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

Subtask #2

75.0 / 75.0

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