All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Hasan and Trip
Tag(s):

Dynamic Programming, Easy-Medium

Problem
Editorial
Analytics

Hasan has finally finished his final exams and he decided to go in a trip among cities in Syria.

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

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

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

Help Hasan by choosing a sequence of cities to visit which maximizes his happiness.

Input format:

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 format:

Output one number rounded to 6 digits after floating point, the maximum possible happiness Hasan can get.

Constraints:

  • 1 <= N <= 3,000
  • 0 <= Xi, Yi, Fi <= 100,000
SAMPLE INPUT
3
0 0 1
3 1 1
6 0 9
SAMPLE OUTPUT
4.675445
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Craftsvilla

Challenge Name

Craftsvilla Backend Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?