Why I am getting TLE in CHEFCUP problem as the constraints are too small? Can somebody help me ?

Problem link - https://www.codechef.com/problems/CHEFCUP

My solution link - https://www.codechef.com/viewsolution/19354758

I have done the solution in O(n) time complexity but still getting TLE instead of having small constraints.
Please help.

The time complexity of your solution is not O(N) it is O(T*A)
As your solution has two loops, to solve this you have to use differentiation and find maximum volume
The time complexity of the solution should be O(T) as T=5*10^5

Here is my solution link

1 Like

@osho_garg Given time limit is of whole input file.

constraints are too large.
Your soln O(T*n) ~ O(500000*50000) in worst case.

Ok, Thanks. Please clear my doubt-

  1. While calculating time complexity should we have to consider the loop of test cases also?
    The time limit that is given in the problem is for 1 test case or for the whole file input?

Ok. But In Codeforces it is given " time limit per test: 1 sec".
Does it means that whole input file for 1 sec or for per test case?

@osho_garg
It means for the whole file
Also in codeforces the “time limit per test: 1 sec” means 1 sec for the whole input file
If you want for information about time limit go here

Thanks @joeyndchandler. I had always neglected this fact.

Generally, CF have one test case per input file. A time limit per test: 1 sec . Here test case is one input file. So If a proplem says take input t. no of test cases then It means that all t test cases have combined time limit of 1 sec.