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

general
,
1

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.

2

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
3

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

4

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?
5

@osho_garg Given time limit is of whole input file.

6

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?

7

@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

8

Thanks @joeyndchandler. I had always neglected this fact.

9

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.