제출 #1254432

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

numbers

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

#define int int64_t

int dp[10][10][20][2];

signed main() {
  int a[2];
  cin >> a[0] >> a[1];
  a[0] --;
  int ans[2];
  for(int _ = 0; _ < 2; _++) {
    if (a[_] <= 0) {
      ans[_] = 0;
      continue;
    }
    string s = to_string(a[_]);
    memset(dp, 0, sizeof(dp));
    for (int k = 19; k >= 0; k--) {
      for (int l = 0; l < 2; l++) {
        for (int i = 0; i < 10; i++) {
          for (int j = 0; j < 10; j++) {
            if (k >= s.size()) {
              dp[i][j][k][l] = 1;
              continue;
            }
            if (l) {
              for (int num = 0; num < 10; num++) {
                if (num != i && num != j) {
		  dp[i][j][k][l] += dp[j][num][k + 1][1];
                }
              }
            } else {
	      int lim = s[k] - '0';
              for (int num = 0; num < lim; num++) {
                if (num != i && num != j) {
		  dp[i][j][k][l] += dp[j][num][k + 1][1];
                }
              }
              if (lim != i && lim != j) {
		dp[i][j][k][l] += dp[j][lim][k + 1][0];
              }
            }
          }
        }
      }
    }
    ans[_] = 1;
    int lim = s[0] - '0';
    for (int num = 1; num <= lim; num++) {
      ans[_] += dp[num][num][1][(num == lim ? 0 : 1)];
    }
    for (int k = 2; k <= s.length(); k++) {
      for (int num = 1; num < 10; num++) {
	ans[_] += dp[num][num][k][1];
      }
    }
  }
  cout << ans[1] - ans[0] << '\n';
}

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