My issue
in this ques the constraint are:
1<=t<=1e4
1<=N<=2e5
so even a O(n) solution leads to 2e9 operations which should exceed the time limit of 1 sec.
This is what I was thinking and tried to solve it in constant time. and I even got a solution but not able to implement so when I saw others solution they have done a O(n) solution. Please tell what am I doing wrong while judging the acceptable time complexity.
My code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,c,n) for(int i=c;i<n;i++)
#define all(x) x.begin(),x.end()
#define pb push_back
void solve(){
ll n,k,h;cin>>n>>k>>h;
ll ans=0;
for(ll a=1;a<=n;a++){
if(a<h){
ll b=(h-a)%(k-1)==0?a-((h-a)/(k-1)):a-((h-a)/(k-1)+1);
if(b>0) ans+=b;
}
else if(a>=h){
ans+=n;
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t;cin>>t;
while(t--){
solve();
}
}
Problem Link: Amphibian Escape Practice Coding Problem
