Hello, I’m a fairly new guy here, and since I’m bored I thought I’d learn something before college starts. I was scrolling Quora and got to this site - namely the problem COINS. The first builds I made didn’t cache data and as such auto failed on the time limit. However, I fixed that with a hash table and got my code to look like this:
#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef unordered_map<int, long long> Map;
long long cMax(Map *orig, int val)
{
if((*orig).find(val) == (*orig).end())
{
long long sum = cMax(orig, val/2) + cMax(orig, val/3) + cMax(orig, val/4);
(*orig).emplace(val, val < sum ? sum : val);
}
return (*orig).find(val)->second;
}
int main()
{
int n;
Map first = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {7, 7}, {8, 8}, {9, 9}, {10, 10}, {11, 11}};
for(; scanf("%d", &n) != EOF; printf("%d\n", cMax(&first, n)));
}
When I test it on ideone for 10 large numbers (mostly few hundred millions typed at random), my execution time is as expected 0s. However, whenever I submit the code on here, it just gives me the Time Limit Exceeded error. I’m probably looking like an idiot because of how many submissions I’ve spammed in the span of an hour. I kind of assume that the problem is with input, as my code really does work when I test it manually or when I test it with ideone. As I’m new, I’m probably missing some IO norm. What is even weirder is that ideone shows 15MB memory usage, while CodeChech shows 8GB! Yikes! Well, I’m not saying it must be IO, but in any case, I consider that this is my fault.
Could anyone enlighten me as to what I’m doing incorrectly?
EDIT: Here’s an ideone run: https://ideone.com/GiIDME, also I know that my printf is not printing longs, still shouldn’t cause a TLE error…