Databases
StackOverflow2013
Postsdbo
PORemoval of billboards from given ones
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PORemoval of billboards from given ones
    primarykey
    data
    text
    <p>I came across this question </p> <blockquote> <p>ADZEN is a very popular advertising firm in your city. In every road you can see their advertising billboards. Recently they are facing a serious challenge , MG Road the most used and beautiful road in your city has been almost filled by the billboards and this is having a negative effect on<br> the natural view. On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road. You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards. ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration. Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.</p> <p>Input description</p> <p>1st line contain two space seperated integers N and K. Then follow N lines describing the profit value of each billboard i.e ith line contains the profit value of ith billboard.</p> <pre><code> Sample Input 6 2 1 2 3 1 6 10 Sample Output 21 </code></pre> <p>Explanation </p> <p>In given input there are 6 billboards and after the process no more than 2 should be together. So remove 1st and 4th billboards giving a configuration _ 2 3 _ 6 10 having a profit of 21. No other configuration has a profit more than 21.So the answer is 21.</p> <pre><code> Constraints 1 &lt;= N &lt;= 1,00,000(10^5) 1 &lt;= K &lt;= N 0 &lt;= profit value of any billboard &lt;= 2,000,000,000(2*10^9) </code></pre> </blockquote> <p>I think that we have to select minimum cost board in first k+1 boards and then repeat the same untill last,but this was not giving correct answer for all cases. i tried upto my knowledge,but unable to find solution. if any one got idea please kindly share your thougths.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMartijn Pieters
    1. USSiva Krishna Aleti
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PORemoval of billboards from given ones
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PORemoval of billboards from given ones
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PORemoval of billboards from given ones
      1. This table or related slice is empty.
      1. VTUpMod
    1. COso is this homework?
      singulars
      1. PORemoval of billboards from given ones
      1. USsoulcheck
    2. COpossible duplicate of [Algorithm to find maximum sum of elements in an array such that not more than k elements are adjacent](http://stackoverflow.com/questions/10045944/algorithm-to-find-maximum-sum-of-elements-in-an-array-such-that-not-more-than-k)
      singulars
      1. PORemoval of billboards from given ones
      1. USFlexo
    3. CO@HighPerformanceMark Mine does! ;)
      singulars
      1. PORemoval of billboards from given ones
      1. USJ. Steen
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload