Find the sequence of cities to visit according to coordinates and conditions

One fine day when Sozy returned to her hometown she met Mega and had a crush on her. After a weeks time Mega went to America. So Sozy too decided to go to America.

There are N cities in America and they are numbered from 1 to N, each city has coordinates on plane, i-th city is in (Xi, Yi).

Sozy is in first city and she wants to visit some cities by car in the trip but the final destination should be N-th city and the sequence of cities she will visit should be increasing in index (i.e. if she is in city i she can move to city j if and only if i < j ).

Visiting i-th city will increase Sozy’s happiness by Fi units (including first and last cities), also Sozy doesn’t like traveling too much, so her happiness will decrease by total distance traveled by her.

Help Sozy by choosing a sequence of cities to visit which maximizes her happiness.

Input:
First line contain integer N.
Next N lines contains three integers each, i-th line contains coordinates of i-th city Xi, Yi and Fi.

Output:
Print the output one number rounded to 6 digits after floating point, the maximum possible happiness Sozy can get.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
double dp[1000],x[1000],y[1000],f[1000];
double get_dist(int a,int b)
{
  return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int main()
{
  double *X=(double*)malloc(3000*sizeof(double));
  double *Y=(double*)malloc(3000*sizeof(double));
  double *F=(double*)malloc(3000*sizeof(double));
  int n,i,j;
  scanf("%d",&n);
  for(i=1;i<=n;i++){
  scanf("%lf %lf %lf",&x[i],&y[i],&f[i]);
  dp[i]=-1e9;}
  dp[1]=0;
  for(i=1;i<=n;i++)
  {
  dp[i]+=f[i];
  for (j=i+1;j<=n;j++){
  double D=get_dist(i,j);
  dp[j]=dp[j]>dp[i]-D?dp[j]:dp[i]-D;
  }
  }
  printf("\n%0.6f\n",dp[n]);
return 0;
}

INPUT_1:
5
7 3 4
6 1 0
4 2 6
7 2 1
5 4 5

OUTPUT:
9.601654

INPUT_2:
7
12 3 7
5 9 2
6 2 4
5 8 2
8 1 4
5 2 5
9 0 3

OUTPUT:
8.266956

ILLUSTRATION

Executed using gcc (-lm for math header file)

Morae Q!