Submission #1632140
Source Code Expand
#pragma region include #include <iostream> #include <iomanip> #include <stdio.h> #include <sstream> #include <algorithm> #include <iterator> #include <cmath> #include <complex> #include <string> #include <cstring> #include <vector> #include <tuple> #include <bitset> #include <queue> #include <complex> #include <set> #include <map> #include <stack> #include <list> #include <fstream> #include <random> //#include <time.h> #include <ctime> #pragma endregion //#include ///////// #define REP(i, x, n) for(int i = x; i < n; ++i) #define rep(i,n) REP(i,0,n) #define ALL(X) X.begin(), X.end() ///////// #pragma region typedef typedef long long LL; typedef long double LD; typedef unsigned long long ULL; typedef std::pair<LL,LL> PLL;// typedef std::pair<int,int> PII;// #pragma endregion //typedef ////定数 const int INF = (int)1e9; const LL MOD = (LL)1e9+7; const LL LINF = (LL)1e18+20; const LD PI = acos(-1.0); const double EPS = 1e-9; ///////// using namespace::std; /* thx http://dwango2016-honsen.contest.atcoder.jp/submissions/679288 */ vector<LL> Nnum;// LL N; void make_Nnum(){ LL ter2,ter5; ter2 = 2; ter5 = 5; Nnum.push_back( ter2 ); Nnum.push_back( ter5 ); for(int index=0;ter2<=N && ter5<=N;++index){ if( index&1 ){ ter2 = ter2*10 + 2; ter5 = ter5*10 + 5; }else{ ter2 = ter2*10 + 5; ter5 = ter5*10 + 2; } Nnum.push_back( ter2 ); Nnum.push_back( ter5 ); } } map<LL,LL> memo; LL dfs(LL num){ if( num == 0 ) return 0; if( memo.find(num) != memo.end() ){ return memo[num]; } LL ret = num; vector<LL>::iterator itr,end; itr = Nnum.begin(); end = Nnum.end(); for(;itr!=end;++itr){ LL val = (*itr); if( val > num ) break; ret = min(ret,num%val + dfs(num/val) ); } memo[num] = ret; return ret; } void solve(){ cin >> N; make_Nnum(); LL ans = dfs(N); cout << ans << endl; } #pragma region main signed main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;//小数を10進数表示 cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別 solve(); } #pragma endregion //main()
Submission Info
Submission Time | |
---|---|
Task | A - 通勤 |
User | akarin55 |
Language | C++14 (GCC 5.4.1) |
Score | 80 |
Code Size | 2206 Byte |
Status | AC |
Exec Time | 37 ms |
Memory | 1536 KB |
Judge Result
Set Name | Sample | Subtask0 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 50 / 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 | AC | 1 ms | 256 KB |
sample1.txt | AC | 1 ms | 256 KB |
sample2.txt | AC | 1 ms | 256 KB |
sample3.txt | AC | 1 ms | 256 KB |
subtask0_0.txt | AC | 1 ms | 256 KB |
subtask0_1.txt | AC | 1 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 | 1 ms | 256 KB |
subtask0_15.txt | AC | 2 ms | 256 KB |
subtask0_2.txt | AC | 2 ms | 256 KB |
subtask0_3.txt | AC | 1 ms | 256 KB |
subtask0_4.txt | AC | 2 ms | 256 KB |
subtask0_5.txt | AC | 1 ms | 256 KB |
subtask0_6.txt | AC | 1 ms | 256 KB |
subtask0_7.txt | AC | 1 ms | 256 KB |
subtask0_8.txt | AC | 1 ms | 256 KB |
subtask0_9.txt | AC | 1 ms | 256 KB |
subtask1_0.txt | AC | 27 ms | 1280 KB |
subtask1_1.txt | AC | 28 ms | 1280 KB |
subtask1_10.txt | AC | 1 ms | 256 KB |
subtask1_11.txt | AC | 1 ms | 256 KB |
subtask1_12.txt | AC | 3 ms | 384 KB |
subtask1_13.txt | AC | 4 ms | 384 KB |
subtask1_14.txt | AC | 33 ms | 1408 KB |
subtask1_15.txt | AC | 32 ms | 1408 KB |
subtask1_2.txt | AC | 34 ms | 1536 KB |
subtask1_3.txt | AC | 37 ms | 1536 KB |
subtask1_4.txt | AC | 21 ms | 1152 KB |
subtask1_5.txt | AC | 37 ms | 1536 KB |
subtask1_6.txt | AC | 36 ms | 1536 KB |
subtask1_7.txt | AC | 33 ms | 1408 KB |
subtask1_8.txt | AC | 35 ms | 1536 KB |
subtask1_9.txt | AC | 35 ms | 1536 KB |