Cheapest Operation Ever

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 128M

Authors:
Problem type
Allowed languages
C, C++

Roy is helping the police department of his city in crime fighting. Today, they informed him about a new planned operation. The city has only one road and criminals live there! To catch these criminals, the police department has to recruit some police officers and give each of them $H as wages. A police officer can start his operation from any point A, drive his car to point B in a straight line, and catch all the criminals who live on this way.

The cost of the fuel used = (A - B)^{2}

Thus, find the minimum amount of money spent to catch all the criminals.

Input Format

1st line: Number of criminals (N) and value of H

2nd line: Position of where the criminals live

Output Format

1st line: Minimum amount of money spent.

Constraints

Subtask 1 (20%): 1 \le N \le 10. 0 \le H \le 1000.

Subtask 2 (20%): 1 \le N \le 100. 0 \le H \le 10000.

Subtask 3 (60%): 1 \le N \le 100000. 0 \le H \le 200000.

Subtask 4 (0%): Sample Testcases.

Sample

Input
5 10
1 4 5 6 9
Output
34

Explanation
One police deployed at position 1 = $10

One police deployed at position 4, travel until position 6 = $10 + $(2 × 2) = $14

One police deployed at position 9 = $10

Total = $34

Original Problem Author: Bidhan; Problem Resource: HackerRank


Comments


  • 5
    AvidDay  commented on Aug. 26, 2018, 5:09 p.m.

    206116


  • 1
    sunnylancoder  commented on Aug. 20, 2017, 1:00 p.m.
    1. Are criminals given in order of position?
    2. Are positions of all criminals distinct?

    • 1
      Kirito  commented on Aug. 20, 2017, 1:03 p.m.

      Yes and yes.