oj.uz

답안 #78381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
78381 2018-10-04T13:56:08 Z HellAngel Palindrome-Free Numbers (BOI13_numbers) C++14
73.75 / 100
 3 ms 748 KB 
#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 last2, int last1)
{
    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, last1, d);
    }
    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:26:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos == s.length()) return 1;
        ~~~~^~~~~~~~~~~~~

Subtask #1
13.75 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 524 KB Output isn't correct
3 Correct 2 ms 584 KB Output is correct
4 Incorrect 2 ms 600 KB Output isn't correct
5 Correct 2 ms 600 KB Output is correct
6 Incorrect 2 ms 600 KB Output isn't correct
7 Incorrect 2 ms 600 KB Output isn't correct
8 Incorrect 2 ms 600 KB Output isn't correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 3 ms 600 KB Output is correct
14 Incorrect 3 ms 600 KB Output isn't correct
15 Incorrect 2 ms 600 KB Output isn't correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 2 ms 600 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 660 KB Output is correct
20 Incorrect 2 ms 660 KB Output isn't correct

Subtask #2
60.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 660 KB Output is correct
2 Correct 2 ms 660 KB Output is correct
3 Correct 2 ms 660 KB Output is correct
4 Correct 3 ms 660 KB Output is correct
5 Incorrect 2 ms 720 KB Output isn't correct
6 Correct 3 ms 736 KB Output is correct
7 Incorrect 2 ms 736 KB Output isn't correct
8 Incorrect 2 ms 736 KB Output isn't correct
9 Incorrect 2 ms 736 KB Output isn't correct
10 Incorrect 2 ms 736 KB Output isn't correct
11 Correct 2 ms 736 KB Output is correct
12 Incorrect 2 ms 736 KB Output isn't correct
13 Incorrect 3 ms 736 KB Output isn't correct
14 Incorrect 2 ms 748 KB Output isn't correct
15 Incorrect 2 ms 748 KB Output isn't correct
16 Correct 3 ms 748 KB Output is correct
17 Correct 3 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Correct 2 ms 748 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 3 ms 748 KB Output is correct
22 Correct 3 ms 748 KB Output is correct
23 Correct 3 ms 748 KB Output is correct
24 Correct 3 ms 748 KB Output is correct
25 Correct 3 ms 748 KB Output is correct
26 Correct 2 ms 748 KB Output is correct
27 Correct 3 ms 748 KB Output is correct
28 Correct 2 ms 748 KB Output is correct
29 Correct 3 ms 748 KB Output is correct
30 Correct 3 ms 748 KB Output is correct
31 Correct 2 ms 748 KB Output is correct
32 Correct 2 ms 748 KB Output is correct
33 Correct 2 ms 748 KB Output is correct
34 Correct 3 ms 748 KB Output is correct
35 Correct 2 ms 748 KB Output is correct
36 Correct 2 ms 748 KB Output is correct
37 Correct 2 ms 748 KB Output is correct
38 Correct 3 ms 748 KB Output is correct
39 Correct 3 ms 748 KB Output is correct
40 Correct 2 ms 748 KB Output is correct
41 Correct 3 ms 748 KB Output is correct
42 Correct 2 ms 748 KB Output is correct
43 Correct 3 ms 748 KB Output is correct
44 Correct 2 ms 748 KB Output is correct
45 Correct 2 ms 748 KB Output is correct