제출 #1287501

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

numbers

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
ll dp[20][2][11][11];
string s;

ll f(int pos, bool lead, int a, int b, bool tight){
  if(pos == s.size()) return 1;
  if(!tight && dp[pos][lead][a][b]) return dp[pos][lead][a][b];
  int lim = tight? (s[pos] - '0'):9;
  ll res = 0;
  for(int i = 0; i <= lim; i++){
    bool nlead = lead;
    int c = a, d = b;
    if(!lead && i == 0){
      nlead = false;
      c = d = 10;
    }
    else{
      if(!lead && d > 0){
        nlead = true;
        d = 10, c = i;
      }
      else{
        if(a != 10 && a == i) continue;
        if(b != 10 && b == i) continue;
        d = a, c = i;
      }
    }
    res += f(pos+1, nlead, c, d, tight && (i == lim));
  }
  if(!tight) dp[pos][lead][a][b] = res; 
  return res;
}

ll get(ll x){
  s = to_string(x);
  memset(dp, 0, sizeof(dp));
  return f(0, 0, 10, 10, 1);
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  ll a, b; cin >> a >> b;
  cout << get(b) - get(a-1);
  return 0;
}

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