getting WA .please help.
thnx ahmedtai
This is also working. Even simpler
#include
using namespace std;
int main() {
int N,T,ans;
cin>>T;
while(T–)
{
cin>>N;
ans = N;
while(N!=0)
{
ans = ans + N;
N–;
}
cout<<ans<<endl;
}
}
Why is Dynamic Programming solution giving TLE?
#include<bits/stdc++.h>
using namespace std;
long long int arr[100001];
inline void scani(int *a){
register char c=0;
while (c<33) c=getchar();
*a=0;
while (c>33)
{
*a=a10+c-‘0’;
c=getchar();
}
}
int main(void)
{
int t,i,n;
scani(&t);
arr[0]=0;
arr[1]=2;
arr[2]=5;
while(t–)
{
scani(&n);
for(i=3;i<=n;++i)
{
arr[i]=i+i+1+arr[i-2];
}
printf("%lld\n",arr[n]);
}
}
@aijajkhan see this solution → CodeChef: Practical coding for everyone
Here i precomputed the cost of all the lights from 0 to 10^5. Then displayed them as the value is entered.
I’m getting TLE inspite of using DP.Please help.
here’s the link to my solution:
https://www.codechef.com/viewsolution/10871878
overflow ??
???
you must have used int datatype which will not work.
It’s because of overflow, n has upper limit as 10^5 so n^n will give you 10^10 which we can not hold in int data type, use long or long long for this purpose.
you are using %d in scanf, but 10^5 is beyond limits of int. see http://www.cplusplus.com/reference/climits/
U dint bracket the n*(n+3) . In your solution, n+3 gets divided by 2 first and then multiplied by n . But what if n+3 isn’t even divisible by 2? You should first multiply n and n+3 and then divide by 2.
Take n as unsigned long long or typecast them to long long while calculating as unsigned long long ans=((long long)n*(long long) (n+3))/2;
Yes, you need to typecast as well. Or take n to be long long int right from the start.
Use long long int result[100001] instead of int result[100001]
You are welcome
For n=5, distance is: 5+5+4+3+2+1.
So n*(n+1)/2 + n works fine here.
10^5 * 10^5 = 10^10. So, use long long to avoid overflow.
i also found new formula
1+2+3+…+ n = n(n+1)/2
n + (n * (n+1)/2);
sum formula + n;
after getting lot of tle…