Submission #20667025

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chabsmin(T& a, T b){
  if (abs(a) > abs(b)){
    a = b;
    return true;
  }
  return false;
}

int popc(int bm)
{
  int r = 0;
  while (bm){
    if (bm&1) r++;
    bm >>= 1;
  }
  return r;
}

ll dp[17][1 << 10][2];

int main()
{
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();

  for (int i = 0; i <= n; i++){
    for (int j = 0; j < (1 << 10); j++){
      dp[i][j][0] = INF;
      dp[i][j][1] = INF;
    }
  }

  dp[0][0][0] = 0;
  for (int i = 0; i < n; i++){
    for (int bm = 0; bm < (1 << 10); bm++){
      for (int j = 0; j < 2; j++){
	if (dp[i][bm][j] < INF){
	  int x = s[i] - '0';
	  for (int d = 0; d < 10; d++){
	    int bm1 = bm | (1 << d);
	    if (i == 0 && d == 0){ bm1 = bm; }
	    if (popc(bm1) <= k){
	      ll diff = dp[i][bm][j] * 10 + (x - d);
	      if (diff >= 0){
		chabsmin(dp[i+1][bm1][0], diff);
	      } else {
		chabsmin(dp[i+1][bm1][1], diff);
	      }
	    }
	  }
	}
      }
    }
  }


  ll ans = INF;
  for (int bm = 0; bm < (1 << 10); bm++){
    for (int j = 0; j < 2; j++){
      ans = min(ans, abs(dp[n][bm][j]));
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result