236852026-01-27 17:16:56abcdSzivárványszámokcpp17Wrong answer 28/451ms548 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int maxn=76;
ll dp[maxn][10][2][2];
string s;
int n;

ll cnt(int pos,int dig,bool tight,bool up){
    if(pos==n)return 1;
    if(dp[pos][dig][tight][up]!=-1)return dp[pos][dig][tight][up];
    ll res=0;
    int lim=tight?s[pos]-'0':9;
    for(int i=0;i<=lim;i++){
        if(i==dig)res+=cnt(pos+1,i,tight&&i==lim,up);
        if(i>dig&&!up)res+=cnt(pos+1,i,tight&&i==lim,false);
        if(i>dig&&up)continue;
        if(i<dig)res+=cnt(pos+1,i,tight&&i==lim,true);
    }
    return dp[pos][dig][tight][up]=res;
}

int main(){
    cin>>s;
    n=s.size();
    memset(dp,-1,sizeof(dp));
    cout<<cnt(0,0,true,false)-1<<'\n';
}
SubtaskSumTestVerdictTimeMemory
base28/45
1Accepted0/01ms316 KiB
2Accepted0/01ms508 KiB
3Wrong answer0/01ms500 KiB
4Accepted1/11ms316 KiB
5Accepted1/11ms316 KiB
6Wrong answer0/11ms316 KiB
7Accepted1/11ms316 KiB
8Accepted1/11ms316 KiB
9Accepted1/11ms316 KiB
10Accepted1/11ms316 KiB
11Accepted1/11ms316 KiB
12Accepted1/11ms316 KiB
13Accepted2/21ms316 KiB
14Accepted2/21ms316 KiB
15Wrong answer0/21ms316 KiB
16Wrong answer0/21ms332 KiB
17Accepted1/11ms508 KiB
18Accepted2/21ms320 KiB
19Accepted2/21ms324 KiB
20Accepted2/21ms508 KiB
21Accepted3/31ms316 KiB
22Accepted2/21ms500 KiB
23Wrong answer0/21ms316 KiB
24Wrong answer0/21ms316 KiB
25Accepted2/21ms316 KiB
26Wrong answer0/21ms316 KiB
27Wrong answer0/21ms316 KiB
28Accepted2/21ms548 KiB
29Wrong answer0/21ms316 KiB
30Wrong answer0/21ms428 KiB