I have recently started programming in C++ and also started coding on Sphere Online Judge.
However, my solution got rejected as it exceeded the time limit.
Please have a look at my code and tell me what I should do to improve the running time.
generally looking at your code, I can add a couple of points.
- always do pre-increment to save couple of cycles unless it matters.
- don't unnecessary do I/O.
- You looks to be using C++, declare variables when they are actually required and not at the start of the function. This is 'C' style programming. This can sometimes save a lot of time.
- There are so many loop going from 0 - n; Surely there must be a way to reduce those.
This is just for the information -
All these are general rules and one cannot tell where the most of the time is consumed. professionally its done by performance analysis tools like gprof. These tools will tell you who's the culprit and then you can devote your time in specific part of the code rather than trying to find issues in the whole code. The tool is not tough to use. This generates a flat file and there are front ends to this tools also which can graphically depict all the paths of the code.
Now there are two things here - a part of code which takes 10 seconds and is called once. There is other part of code which takes .5 seconds but its called 50 times. So sometimes its tricky.
I actually read somewhere that dynamic allocation of array takes a longer time. So, I defined a,p in the beginning.
Now the judge tells me that I have a segmentation fault.
However, the program runs perfectly on Dev C++.
Where could the error be now?