Submission #1758395


Source Code Expand

#include <iostream>
#include <map>
#include <vector>
using namespace std;

using ll = long long int;

ll n, m, s;
map<ll, ll> dp;
vector<ll> arr;

ll DP(ll num) {
	if (dp[num]) { return dp[num]; }
	ll mini = num;
	if (num <= 1) {
		return num;
	}
	for (auto i : arr) {
		ll a = num / i,b=num % i;
		if (a != 0) { mini = min(mini, DP(a) + b); }
	}
	return dp[num]=mini;
}

int main(void){
    
    cin >> n;
    
    arr.push_back(2);
    arr.push_back(5);
    
    for(int i = 1; i <= 17; i++){
        arr.push_back(arr[2*(i-1)] * 10 + (( i % 2 ) ? 5 : 2 ));
        arr.push_back(arr[2*(i-1)+1] * 10 + (( (i) % 2 ) ? 2 : 5 ));
    }
    
    cout << DP(n) << endl;
    
}

Submission Info

Submission Time
Task A - 通勤
User nasatame
Language C++14 (GCC 5.4.1)
Score 80
Code Size 713 Byte
Status AC
Exec Time 41 ms
Memory 1536 KB

Judge Result

Set Name Sample Subtask0 All
Score / Max Score 0 / 0 30 / 30 50 / 50
Status
AC × 4
AC × 20
AC × 36
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 1 ms 256 KB
subtask0_2.txt AC 1 ms 256 KB
subtask0_3.txt AC 1 ms 256 KB
subtask0_4.txt AC 1 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 31 ms 1280 KB
subtask1_1.txt AC 31 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 5 ms 384 KB
subtask1_14.txt AC 38 ms 1408 KB
subtask1_15.txt AC 37 ms 1408 KB
subtask1_2.txt AC 38 ms 1408 KB
subtask1_3.txt AC 41 ms 1536 KB
subtask1_4.txt AC 24 ms 1024 KB
subtask1_5.txt AC 41 ms 1536 KB
subtask1_6.txt AC 40 ms 1536 KB
subtask1_7.txt AC 37 ms 1408 KB
subtask1_8.txt AC 40 ms 1536 KB
subtask1_9.txt AC 40 ms 1536 KB