VERY IMPORTANT NOTE!!!! PLEASE

DONT COPY PASTE FROM PREVOUS CHEGG ANSWERS!

Code must be written in C Language/ UBUNTU environment.

you need to provide a brief explanation of your codes and the efficiency analysis with comments.

input1: 3 // number of destinations 1 2 // i = 1, xi=2 2 3 // i = 2, xi=3 3 6 // i = 3, xi=6 2 // k=2 number of stops

output1: 2 6 (for i=1 unhappiness = (2-2)^2 =0, for i=2 unhappiness = (3-2)^2 =1, for i=3 unhappiness = (6-6)^2 =0) or 3 6 (for i=1 unhappiness = (2-3)^2 =1, for i=2 unhappiness = (3-3)^2 =0, for i=3 unhappiness = (6-6)^2 =0)

input2: 3 // number of destinations 1 2 // i = 1, xi=2 2 3 // i = 2, xi=3 3 6 // i = 3, xi=6 1 // k=1 number of stops

output2: 3 (for i=1 unhappiness = (2-3)^2 =1, for i=2 unhappiness = (3-3)^2 =0, for i=3 unhappiness = (6-3)^2 =9)

1. Assume there is a bus company serving along a highway with m km and there are n people using this company for travel. They all board the bus at the starting point 0, and each passenger i specifies a destination xi for the travel before boarding(xi here indicates the distance from the destination to the starting point). If the passenger i leaves the bus at a position y, then the unhappiness of the passenger i will be (Xi - y)2. There are no fixed bus stops. All the stops will be determined after gathering the destinations from all the passengers, and the bus can make at most k stops. Devise a dynamic programming algorithm that takes n destinations X1, ... , Xn and an integer kas input, and outputs an optimal set of positions for k stops that minimizes the sum of the unhappiness of all the passengers. Note that all the inputs given to the algorithm are assumed to be integers and the Xi values are given as sorted in increasing order