Codechef Deforestation problem: Finding maximum rope length between trees Here is the CodeChef page to the problem.  Given N trees, each at x-position x with height T, string a rope between two trees Ti and Tj such that:


A rope connecting the tops of the trees is at 45 degrees from the x-axis
The rope does not pass through any other trees
The length of the rope, minus the total height reduction by cutting trees, is maximized
Trees Ti and Tj themselves are not cut


Here is my code that need to process 100 &times; 250,000 data in less than 3&nbsp;seconds (I don't know the exact spec of the running machine).  As I'm quite new to coding, what can I improve or change to make it faster, and more optimized?

// codechef_deforestation.cpp : définit le point d'entrée pour l'application console.
//

#include &lt;iostream&gt;
#include &lt;iomanip&gt;
#include &lt;vector&gt;
#include &lt;cmath&gt;
#include &lt;ctime&gt;

int main()
{
    clock_t startTime = clock();
    //Read input
    freopen("C:\\somepath\\input.in", "r", stdin);
    freopen("C:\\somepath\\output.out", "w", stdout);
    int t;
    std::cin &gt;&gt; t;
    //std::cout &lt;&lt; t &lt;&lt; std::endl;
    for (int i = 0; i &lt; t; i++)
    {
        double result = -1;
        int n;
        std::cin &gt;&gt; n;
        //std::cout &lt;&lt; t &lt;&lt; std::endl;
        std::vector &lt;int&gt; x, h;
        x.resize(n);
        h.resize(n);
        //chargement des données
        for (int j = 0; j &lt; n; j++)
        {
            std::cin &gt;&gt; x[j] &gt;&gt; h[j];
            //std::cout &lt;&lt; x[j] &lt;&lt; h[j] &lt;&lt; std::endl;
        }
        //calcul
        for (int j = 0; j &lt; n; j++)
        {
            for (int k = j+1; k &lt; n; k++)
            {
                //std::cout &lt;&lt; "k : " &lt;&lt; k &lt;&lt; std::endl;
                int diff_x = x[k] - x[j];
                int diff_h = h[k] - h[j];
                if (diff_x == diff_h) //si 45 deg
                {
                    double res_int = sqrt(diff_x*diff_x + diff_h* diff_h);
                    for (int l = j + 1; l &lt; k; l++)
                    {
                        //std::cout &lt;&lt; "l : " &lt;&lt; l &lt;&lt; std::endl;
                        if (h[l] &gt; x[l])
                        {
                            res_int = res_int - (h[l] - x[l]);
                        }
                    }
                    if (res_int &gt; result)
                    {
                        result = res_int;
                    }
                }
            }   
        }
        std::cout &lt;&lt; std::setprecision(6) &lt;&lt; std::fixed &lt;&lt; result &lt;&lt; std::endl;
        x.clear();
        h.clear();
    }
    clock_t testTime=clock();
    std::cout &lt;&lt; testTime - startTime;
    return 0;
}


The freopen() function needs to stay.
There appears to be a bug in your program. In particular, I think this line is wrong:

if (h[l] &gt; x[l])


Starting from location j, the question is not whether h[l] &gt; x[l] but whether h[l] - h[j] &gt; x[l] - x[j]. The 45 degree angle will be relative to the start-point of the line, not the origin, I think.

That said, your loop over l is duplicating the results of looping over k. I think you could profit by keeping a running total of lossage during your k loop, and just adding it in when appropriate.

Viz:

for (j...)
    auto hj = h[j], xj = x[j];

    for (k...)
        auto dx = x[k] - xj;
        auto dh = h[k] - hj;

        auto over_height = dh - dx;

        if (over_height &gt; 0) deforestation += over_height;

        if (over_height == 0) {
            // this k is a candidate
            rope_len = sqrt(...) - deforestation;

        }