제출 #1256888

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

numbers

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int N = 10;
int dp[2 * N][N + 1][N + 1][2], len; // dp[pos][i][j][smaller] -> i sonrakine aktarılan 2 önceki, j -> sonrakine aktarılan 1 önceki eleman eğer i veya j 10 ise sonrakine eleman kısıtlaması aktarılmıyor (başlangıç) 
string s;

inline int calc(int a){
	if(a < 0) return 0ll;
    memset(dp, 0, sizeof(dp));
    dp[0][10][10][0] = 1;
    s.clear();
    while(a){
        s += ('0' + a % 10);
        a /= 10;
    }
    reverse(s.begin(), s.end());
    len = sz(s) / 2 + (sz(s) & 1);
    for(int pos = 0; pos < sz(s); pos++){
        for(int i = 0; i <= 10; i++){
            for(int j = 0; j <= 10; j++){
				if(i == j && i != 10) continue;
                for(int smaller = 0; smaller < 2; smaller++){
                    for(int num = 0; num < 10; num++){
                        if(num == i || num == j || (!smaller && num > s[pos] - '0')) continue;
                        dp[pos + 1][num][i][smaller || num < s[pos] - '0'] += dp[pos][i][j][smaller];
                    }
                }
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            if(i == j) continue;
            ans += dp[sz(s)][i][j][0] + dp[sz(s)][i][j][1];
        }
    }
    return ans;
}

inline void solve(){
    int a, b;
    cin >> a >> b;
    int vala = calc(a - 1), valb = calc(b);
    int palnum = valb - vala;
    cout << palnum << "\n";
    return;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
	return 0;
}

• Subtask 1: 12.5 / 25
• Subtask 2: 60 / 75