Submission #1756160


Source Code Expand

#include <bits/stdc++.h>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n - 1); i >= 0; --i)
#define mod 1000000007
#define INF 93193111451418101
#define MIN -93193111451418101
//#define INF 931931114518101
using namespace std;
typedef pair<ll, ll> P;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
#define yo 100001
//------------------変数-----------------------//
ll d, n, m;
map<P, ll> dp;
string str[100];
//-------------------関数----------------------//
ll mintime = INF;
ll DP(ll L, ll num, ll kaisuu) {
  if (num == n) {
    mintime = min(mintime, kaisuu);
    return 0;
  }
  if ((n - num) % L) {
    return INF;
  }
  if (kaisuu > mintime) {
    return INF;
  }
  if (dp[P(L, num)]) {
    return dp[P(L, num)];
  }
  ll cnt = INF;
  for (ll i = 39; i >= 0; i--) {
    if (to_string(L).size() + str[i].size() < 18) {
      ll izryt = L * stoll(str[i]);
      if (num + izryt <= n && izryt != L) {
        cnt = min(cnt, DP(izryt, num + izryt, kaisuu + 1) + 1);
      }
      if (num + izryt <= n && izryt != L) {
        cnt = min(cnt, DP(izryt, num, kaisuu));
      }
    }
  }
  cnt = min(cnt, n - num);

  return dp[P(L, num)] = cnt;
}

int main() {
  cin >> n;
  str[0] = '1';
  str[1].push_back('2');
  str[2].push_back('5');
  FOR(i, 3, 40) {
    auto a = stoll(str[i - 2]) % 10;
    if (a == 5) {
      str[i] = str[i - 2] + "2";
    } else {
      str[i] = str[i - 2] + "5";
    }
  }
  cout << DP(1, 0, 0) << endl;
  return 0;
}

Submission Info

Submission Time
Task A - 通勤
User keidaroo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1764 Byte
Status WA
Exec Time 53 ms
Memory 768 KB

Judge Result

Set Name Sample Subtask0 All
Score / Max Score 0 / 0 0 / 30 0 / 50
Status
AC × 2
WA × 2
AC × 10
WA × 10
AC × 14
WA × 22
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask0 sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_15.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt
All sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_15.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt WA 2 ms 256 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 2 ms 256 KB
sample3.txt WA 2 ms 256 KB
subtask0_0.txt AC 2 ms 256 KB
subtask0_1.txt WA 2 ms 256 KB
subtask0_10.txt AC 1 ms 256 KB
subtask0_11.txt AC 1 ms 256 KB
subtask0_12.txt AC 1 ms 256 KB
subtask0_13.txt AC 1 ms 256 KB
subtask0_14.txt AC 2 ms 256 KB
subtask0_15.txt AC 1 ms 256 KB
subtask0_2.txt AC 2 ms 256 KB
subtask0_3.txt WA 2 ms 256 KB
subtask0_4.txt WA 2 ms 256 KB
subtask0_5.txt WA 2 ms 256 KB
subtask0_6.txt WA 1 ms 256 KB
subtask0_7.txt WA 1 ms 256 KB
subtask0_8.txt WA 1 ms 256 KB
subtask0_9.txt WA 1 ms 256 KB
subtask1_0.txt WA 6 ms 256 KB
subtask1_1.txt WA 9 ms 384 KB
subtask1_10.txt AC 2 ms 256 KB
subtask1_11.txt AC 2 ms 256 KB
subtask1_12.txt AC 2 ms 256 KB
subtask1_13.txt AC 2 ms 256 KB
subtask1_14.txt WA 1 ms 256 KB
subtask1_15.txt WA 53 ms 768 KB
subtask1_2.txt WA 13 ms 384 KB
subtask1_3.txt WA 13 ms 384 KB
subtask1_4.txt WA 11 ms 384 KB
subtask1_5.txt WA 1 ms 256 KB
subtask1_6.txt WA 1 ms 256 KB
subtask1_7.txt WA 1 ms 256 KB
subtask1_8.txt WA 1 ms 256 KB
subtask1_9.txt WA 2 ms 256 KB