6716340 | CodeChef

1

#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

2

Because your code is O(TX)

3

can you give some idea to improve this

4

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