Help me in solving CHFHEIST problem

help
,
1

My issue

HOW IS MY CODE CAUSING TLE ERROR?ONLY USED 1 for{} LOOP

My code

#include <iostream>
using namespace std;

int main() {long long t,D,d,p,q;
cin>>t;
while(t--){long long s=0,n=1;
    cin>>D>>d>>p>>q;
    for(int i=1;i<=D;i++){
        if(i-n*d==1){
            p=p+q;
            s+=p;
            n++;
        }
        else{
            s+=p;
        }
    }
    cout<<s<<endl;
}
	return 0;
}

Problem Link: CHFHEIST Problem - CodeChef

2

@akhon
Because u are iterating till D which can be as big as 10^6 and the number of test cases is 10^5 so the total complexity will become 10^11 which is too much so u have to think of some mathematical solution that can be done in O(1) inside test case loop . Overall u r not allowed to iterate something in this test case because of high constraint.

3

But dont we usually ignore the number of test cases for writing code? Like for any ‘n’ less than 10^9 the code shouldn’t really give TLE error no? I remember doing the same and getting no TLE error.

4

Yes u r right but in such question they have mentioned like the size of tn would not exceed 10^5 or 6 like that. In this case they haven’t mentioned then u have to include t in your time complexity or not.
For ex:-


see this question in the constraints section last point they have mentioned that the Sum of N over all test cases does not exceed 210^5.