제출 #1310379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310379		tuncay_pasha	Palindrome-Free Numbers (BOI13_numbers)	C++20	42.50 / 100	2 ms	1348 KiB

numbers

#include "bits/stdc++.h"
using namespace std;

string s;
int dp[20][2][2][15][15][15];

int check(int a, int b, int c)
{
  if (a == 0 && b == 0 && c == 0) return true;
  if (a == 0 && b == 0) return true;
  if (a == 0 && c == 0) return true;
  if (b == 0 && c == 0) return true;
  if (a == 0) return (b != c);
  if (b == 0) return (a != c);
  if (c == 0) return (a != b);
  return (a != b && a != c && b != c);
}
int solve(int pos, bool f1, bool started, int minus2, int minus1, int curr)
{
  if (pos == s.size()) return check(minus2, minus1, curr);
  if (dp[pos][f1][started][minus2][minus1][curr] != -1) return dp[pos][f1][started][minus2][minus1][curr];
  int res = 0, lim = (f1 ? 9 : s[pos] - '0');
  for (int i = 1; i <= lim + 1; ++i)
  {
    bool nf1 = (f1 || i < (lim + 1));
    if (i == 1 && !started) res += solve(pos + 1, nf1, false, 0, 0, 0);
    else
    {
      int nminus2 = minus1;
      int nminus1 = curr;
      int ncurr = i;
      if (!check(nminus2, nminus1, ncurr)) continue; 
      res += solve(pos + 1, nf1, true, nminus2, nminus1, ncurr);
    }
  }
  return dp[pos][f1][started][minus2][minus1][curr] = res;
}
int get(int n)
{
  s = to_string(n);
  memset(dp, -1LL, sizeof(dp));
  return solve(0, false, false, 0, 0, 0);
}
signed main()
{
  int l, r;
  cin >> l >> r;
  cout << get(r) - get(l - 1) << '\n';
}

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