HCI '16 - Cheapest Operation Ever - DMOJ: Modern Online Judge

HCI '16 - Cheapest Operation Ever

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 0.6s

Memory limit: 128M

Authors:

zj97, damian, fanpu

Problem type

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$ ~\$H~ as wages. A police officer can start his operation from any point $A$ ~A~, drive his car to point $B$ ~B~ in a straight line, and catch all the criminals who live on this way.

The cost of the fuel used $= (A - B)^2$ ~= (A - B)^2~

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

Constraints

Subtask 1 [20%]

$1 \le N \le 10$ ~1 \le N \le 10~

$0 \le H \le 1\,000$ ~0 \le H \le 1\,000~

Subtask 2 [20%]

$1 \le N \le 100$ ~1 \le N \le 100~

$0 \le H \le 10\,000$ ~0 \le H \le 10\,000~

Subtask 3 [60%]

$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~

$0 \le H \le 200\,000$ ~0 \le H \le 200\,000~

Subtask 4 [0%]

Sample test cases.

Input Specification

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

$2$ ~2~nd line: Position of where the criminals live

Output Specification

$1$ ~1~st line: Minimum amount of money spent.

Sample Input

5 10
1 4 5 6 9

Sample Output

Explanation

One police deployed at position $1$ ~1~ $= \$10$ ~= \$10~

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

One police deployed at position $9$ ~9~ $= \$10$ ~= \$10~

Total $= \$34$ ~= \$34~

Original Problem Author: Bidhan; Problem Resource: HackerRank

Comments

0

JY900 commented on Nov. 26, 2020, 4:28 p.m. ← edited →

Does anyone know how I can optimize my code to get $\mathcal{O}(N)$ ~\mathcal{O}(N)~?

4

4fecta commented on Nov. 26, 2020, 5:56 p.m.

https://codeforces.com/blog/entry/63823

2

JY900 commented on Nov. 27, 2020, 3:51 p.m.

took me a while to figure out the query/insert operations, but CHT is a really cool optimization technique!

4

4fecta commented on Feb. 22, 2020, 8:11 p.m.

Copy of a problem from the University of Chicago Invitational Programming Contest 2012: https://www.e-olymp.com/en/problems/3972

10
sunnylancoder commented on Aug. 20, 2017, 5:00 p.m.
Are criminals given in order of position?

Are positions of all criminals distinct?

9

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

Yes and yes.