236862026-01-27 17:17:44abcdSzivárványszámokcpp17Hibás válasz 28/452ms536 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

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

ll cnt(ll pos,ll 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;
    ll lim=tight?s[pos]-'0':9;
    for(ll 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';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base28/45
1Elfogadva0/01ms512 KiB
2Elfogadva0/01ms316 KiB
3Hibás válasz0/01ms316 KiB
4Elfogadva1/11ms316 KiB
5Elfogadva1/11ms316 KiB
6Hibás válasz0/11ms316 KiB
7Elfogadva1/11ms316 KiB
8Elfogadva1/11ms316 KiB
9Elfogadva1/11ms316 KiB
10Elfogadva1/11ms500 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva1/11ms500 KiB
13Elfogadva2/21ms316 KiB
14Elfogadva2/21ms316 KiB
15Hibás válasz0/21ms316 KiB
16Hibás válasz0/21ms512 KiB
17Elfogadva1/11ms500 KiB
18Elfogadva2/21ms388 KiB
19Elfogadva2/21ms316 KiB
20Elfogadva2/22ms508 KiB
21Elfogadva3/31ms536 KiB
22Elfogadva2/21ms316 KiB
23Hibás válasz0/21ms316 KiB
24Hibás válasz0/21ms356 KiB
25Elfogadva2/21ms316 KiB
26Hibás válasz0/21ms332 KiB
27Hibás válasz0/21ms316 KiB
28Elfogadva2/21ms316 KiB
29Hibás válasz0/21ms316 KiB
30Hibás válasz0/21ms316 KiB