Submission #1240977

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




typedef long long ll;
int N;
ll dp[15][15][2];
//-----------------------------------------------------------------------------------
int main() {
    cin >> N;

    string s = to_string(N);
    int n = s.length();
    dp[0][0][1] = 1;
    rep(i, 0, n) rep(j, 0, 11) rep(k, 0, 2) {
        int c = s[i] - '0';

        int ma = 10;
        if (k == 1) ma = c + 1;
        rep(jj, 0, ma) {
            if(k == 1 && jj == c) dp[i + 1][j + (jj == 1)][1] += dp[i][j][k];
            else dp[i + 1][j + (jj == 1)][0] += dp[i][j][k];
        }
    }

    ll ans = 0;
    rep(j, 0, 11) rep(k, 0, 2) ans += dp[n][j][k] * j;
    cout << ans << endl;
}

Submission Info

Judge Result