Submission #1770233


Source Code Expand

#include<bits/stdc++.h>
#define int long long
#define loop(i, a, b) for(int i = a; i < b; i++)
#define rep(i, a) loop(i, 0, a)
#define all(a) (a).begin(),(a).end()
using namespace std;
const int MOD = 1e9 + 7, INF = 1e9;
using vi = vector <int>;
using vvi = vector <vi>;
//g++ -std==c++14 


signed main(){
    int in_a, in_b;
    cin >> in_a >> in_b;
    string a = to_string(in_a - 1), b = to_string(in_b);
    int dp[b.size() + 1][2][2][2] ={};
    dp[0][0][0][0] = 1;

    rep(i, b.size())rep(j, 2)rep(k, 2)rep(l, 2){
        int lim = j ? 9 : b[i] - '0';
        rep(d, lim + 1){
            dp[i + 1][j || d < lim][k || d == 4][l || d == 9] += dp[i][j][k][l];
        }
    }
    int b_0 = dp[b.size()][0][1][0] + dp[b.size()][1][1][0] +
              dp[b.size()][0][0][1] + dp[b.size()][1][0][1] + 
              dp[b.size()][0][1][1] + dp[b.size()][1][1][1];
    
    int dpa[a.size() + 1][2][2][2] = {1};
    rep(i, a.size())rep(j, 2)rep(k, 2)rep(l, 2){
        int lim;
        if(j == 0) lim = a[i] - '0';
        else lim = 9;
        rep(d, lim + 1){
            dpa[i + 1][j || d < lim][k || d == 4][l || d == 9] += dpa[i][j][k][l];
        }        
    }

    int a_0 = dpa[a.size()][0][1][0] + dpa[a.size()][1][1][0] +
              dpa[a.size()][0][0][1] + dpa[a.size()][1][0][1] +
              dpa[a.size()][0][1][1] + dpa[a.size()][1][1][1];

    cout << b_0 - a_0 << endl;
}

Submission Info

Submission Time
Task D - 禁止された数字
User Masumi
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1441 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 4
AC × 16
AC × 39
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask2 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 1 ms 256 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 1 ms 256 KB
subtask0_sample04.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask2_01.txt AC 1 ms 256 KB
subtask2_02.txt AC 1 ms 256 KB
subtask2_03.txt AC 1 ms 256 KB
subtask2_04.txt AC 1 ms 256 KB
subtask2_05.txt AC 1 ms 256 KB
subtask2_06.txt AC 1 ms 256 KB
subtask2_07.txt AC 1 ms 256 KB
subtask2_08.txt AC 1 ms 256 KB
subtask2_09.txt AC 1 ms 256 KB
subtask2_10.txt AC 1 ms 256 KB
subtask2_11.txt AC 1 ms 256 KB
subtask2_12.txt AC 1 ms 256 KB
subtask2_13.txt AC 1 ms 256 KB
subtask2_14.txt AC 1 ms 256 KB
subtask2_15.txt AC 1 ms 256 KB
subtask2_16.txt AC 1 ms 256 KB
subtask2_17.txt AC 1 ms 256 KB
subtask2_18.txt AC 1 ms 256 KB
subtask2_19.txt AC 1 ms 256 KB
subtask2_20.txt AC 1 ms 256 KB
subtask2_21.txt AC 1 ms 256 KB
subtask2_22.txt AC 1 ms 256 KB