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 × 250,000 data in less than 3 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 <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <ctime>
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 >> t;
//std::cout << t << std::endl;
for (int i = 0; i < t; i++)
{
double result = -1;
int n;
std::cin >> n;
//std::cout << t << std::endl;
std::vector <int> x, h;
x.resize(n);
h.resize(n);
//chargement des données
for (int j = 0; j < n; j++)
{
std::cin >> x[j] >> h[j];
//std::cout << x[j] << h[j] << std::endl;
}
//calcul
for (int j = 0; j < n; j++)
{
for (int k = j+1; k < n; k++)
{
//std::cout << "k : " << k << 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 < k; l++)
{
//std::cout << "l : " << l << std::endl;
if (h[l] > x[l])
{
res_int = res_int - (h[l] - x[l]);
}
}
if (res_int > result)
{
result = res_int;
}
}
}
}
std::cout << std::setprecision(6) << std::fixed << result << std::endl;
x.clear();
h.clear();
}
clock_t testTime=clock();
std::cout << testTime - startTime;
return 0;
}
The freopen()
function needs to stay.