Maximize the Earning

 Problem:-

Napoleon choosed a city for Advertising his company’s product. There are 

S

 streets in that city. Each day he travels one street. There are 

N

 buildings in a street which are located at points 

1,2,3….N(

respectively)

. Each building has some height(Say 

h

 meters). Napoleon stands at point 

0

. His height is 

0.5m

. Now Napoleon starts communicating with the people of each building. He can communicate with people of a particular building only if he can see that building. If he succeed to communicate with any particular building then his boss gives him 

Rrupees

. i.e. if he communicates with 

K

 buildings in a day, then he will earn 

KRrupees

. Now Napoleon wants to know his maximum Earning for each day.

Note: All the points are on Strainght Line and Napoleon is always standing at point 0.

Input:
First line of input contains an integer 

S

, denoting no of streets in the city.
Details for each street is described in next two lines.
First line contains two integers 

N

 and 

R

,

 denoting no of buildings in the Street and earning on communicating with a building.
Second line contains 

N

 integers, denoting height of  building.

Output:
Print 

S

 Lines, each containing maximum earning in 

ith

 street.
    
Constraints:
    

1N104


    

1h109


    

1S100


    

1R104

Sample Input
2
6 3
8 2 3 11 11 10
5 12
12 20 39 45 89
Sample Output
6
60
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are two streets in the city.

The first street has 

6

 buildings and the earning of Napoleon for communicating with each building is 

3rupees

.

Height of buildings are 

8,2,3,11,11,10

 respectively.

As Chef is standing at point 

0

, he will be able to see only 1st and 4th building.

So his total earning will be 

32=6rupees

 in that street

Similarly for 2nd street his earning will be 

60rupees


Code:-

#include<stdio.h>
int main()
{
    long int n,s,r,i;
    long long int max,h,building;
    scanf(“%ld”,&s);
    
    while(s–)
    {
        scanf(“%ld%ld”,&n,&r);
         max=0;
        building=0;
    for(i=0;i<n;i++)
        {
      scanf(“%lld”,&h);
      if(h>max)
           {
               max=h;
               building++;
           }
        }
        printf(“%lldn”,r*building);

    }
    return 0;
}



Leave a Reply

Your email address will not be published.