Bytelandian Gold Coins

1

#include <bits/stdc++.h>

using namespace std;

int main()
{
int tc;
cin>>tc;
for(int i=1;i<=tc;i++)
{

    long long int n;
    cin>>n;

    long long int a[n+1];
    a[0] = 0;
    

    for(long long int j =1;j<=n;j++)
    {

        a[j] = max(j,a[j/2] + a[j/3] + a[j/4]);


    }

    cout<<a[n]<<endl;

}

}

/* Can anyone tell me what is wrong with this solution */

2

your method is correct but unfortunately n is of order of 10 raised to9. cpp language can do only 10 raised to 8 operations in 1 second. So it takes 100 second to do all test case.

3

This is a O(n) solution which will not work for the constraints since n <= 10^9. Use recursion instead and store the values in a map or an unordered map.

4

thanks a lot