제출 #1124591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124591		0pt1mus23	Palindrome-Free Numbers (BOI13_numbers)	C++20	33.75 / 100	1 ms	328 KiB

numbers

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 1000+23, inf = INT_MAX, LG = 20,pr = 31;

int mem[30][123][2][2];

int dp(int i,int balaca,int last,int st,string s){
    if(mem[i][last][balaca][st]!=-1){
        return mem[i][last][balaca][st];
    }
    if(i==s.size()){
        return st;
    }
    int res=0;
    if(!st){
        res+=dp(i+1,1,0,0,s); // hele baslama
        if(balaca){
            for(int q =1;q<=9;q++){
                res+=dp(i+1,1,q,1,s);
            }
        }
        else{
            assert(i==0);
            for(int q =1;q<=(s[i]-'0');q++){
                res+=dp(i+1,balaca | (q< (s[i]-'0')), q, 1,s);
            }
        }
    }
    else{
        int l1 = last%10;
        int l2 = (last<10? -1 : (last/10));
        if(balaca){
            for(int q=0;q<=9;q++){
                if(q!=l1 && q!=l2){
                    int nw = l1*10 + q;
                    res+=dp(i+1,1,nw,1,s);
                }
            }
        }
        else{
            for(int q=0;q<=(s[i]-'0');q++){
                if(q!=l1 && q!=l2){
                    int nw = l1*10 + q;
                    res+=dp(i+1, q<(s[i]-'0'),nw,1,s);
                }
            }
        }
    }
    return mem[i][last][balaca][st] = res;
}

int f(int n){
    if(n==0){
        return 0;
    }
    string s="";

    for(int i = 20;i>=0;i--){
        if(!n){
            break;
        }
        s.pb(n%10 +'0');
        n/=10;
    }
    reverse(all(s));

    for(int i =0;i<=23;i++){
        for(int j=0;j<=100;j++){
            for(int t=0;t<=1;t++){
                for(int st=0;st<=1;st++){
                    mem[i][j][t][st]=-1;
                }
            }
        }
    }

    return dp(0,0,0,0,s);
}

void fast(){
    int l,r;
    cin>>l>>r;
    putr(f(r) - f(l-1));
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

• Subtask 1: 13.75 / 25
• Subtask 2: 20 / 75