Railway Caterers

All submissions for this problem are available.
The government of Siruseri has just commissioned one of the longest and most modern railway routes in the world. This route runs the entire length of Siruseri and passes through many of the big cities and a large number of small towns and villages in Siruseri. The railway stations along this route have all been constructed keeping in mind the comfort of the travellers. Every station has big parking lots, comfortable waiting rooms and plenty of space for eateries. The railway authorities would like to contract out the catering services of these eateries. Unfortunately, catering contractors are not philanthropists and would like to maximise their profits. The Siruseri Economic Survey has done a through feasibility study of the different stations and documented the expected profits (or losses) for the eateries in all the railway stations on this route. Every contractor would like to run the catering service only in the profitable stations and stay away from the loss making ones. On the other hand the authorities would like to ensure that every station was catered to. Towards this end, authorities offered to contract out stations in groups. They would fix a minimum size $K$ and a contractor was only allowed to bid for any contiguous sequence of $K$ or more stations. For example suppose there are 8 stations along the line and their profitability is as follows: $ $ Station 1 2 3 4 5 6 7 8 Expected Profits 20 90 30 20 80 70 60 125 $ $ If $K$ was fixed to be $3$, a contractor could pick stations $3, 4, 5$ and $6$. This would give him a total profit of $40$ (i.e. a loss of $40$). He could have picked $3, 4$ and $5$ giving him a profit of $30$. On the other hand if he picked stations $2, 3, 4$ and $5$, he would make a profit of $120$. You can check that this is the best possible choice when $K = 3$. If $K = 1$, then the best choice would be to bid for just station 8 and make a profit of $125$. You have been hired by a contractor. Your task is to help him identify the segment of stations to bid for so at to maximize his expected profit. ###Input: The first line of the input contains two integers $N$ and $K$, where $N$ is the number of stations and $K$ is the minimum number of contiguous stations that must form part or the bid. The next $N+1$ lines (lines $2,...,N+1$) describe the profitability of the $N$ stations. Line $i+1$ contains a single integer denoting the expected profit at station $i$. ###Output: A single integer $P$, indicating the maximum possible profit. ###Constraints:  $1 \leq N \leq 1000000$.  $1 \leq K \leq N$.  You may further assume that in $50 \%$ of the inputs $1 \leq N \leq 5000$. ###Sample Input 1: 8 3 20 90 30 20 80 70 60 125 ###Sample Output 1: 120 ###Sample Input 2: 8 1 20 90 30 20 80 70 60 125 ###Sample Output 2: 125Author:  admin 
Date Added:  17092018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions