6716340 | CodeChef


#include <bits/stdc++.h>
#include
using namespace std;

int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
long long int x,i,j,count=0;
cin>>x;
long long int arr[x+1]={0};
int b[2]={3,2};
arr[0]=1;
arr[2]=1;
arr[3]=1;
for(j=4;j<x+1;j++)
{
for(i=0;i<2;i++)
{
arr[j]+=((arr[j-b[i]])%1000000009);
}
}
cout<<arr[x]%1000000009<<"\n";
}
return 0;
}

why am i get tle in question no. 3(billiards) in dsa learning series

Because your code is O(TX)

can you give some idea to improve this

You don’t want to think of the solution for yourself?