Submission #1756245
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 >= 1; 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)); } } } 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 | 1738 Byte |
Status | WA |
Exec Time | 52 ms |
Memory | 768 KB |
Judge Result
Set Name | Sample | Subtask0 | All | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 50 | ||||||||||||
Status |
|
|
|
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 | 1 ms | 256 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | WA | 1 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 | 1 ms | 256 KB |
subtask0_5.txt | WA | 1 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 | 1 ms | 256 KB |
subtask1_11.txt | AC | 1 ms | 256 KB |
subtask1_12.txt | AC | 1 ms | 256 KB |
subtask1_13.txt | AC | 1 ms | 256 KB |
subtask1_14.txt | WA | 1 ms | 256 KB |
subtask1_15.txt | WA | 52 ms | 768 KB |
subtask1_2.txt | WA | 12 ms | 384 KB |
subtask1_3.txt | WA | 11 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 | 1 ms | 256 KB |