Weird Sum
Practice
3.7 (41 votes)
2d dynamic programming
Algorithms
Dynamic programming
Problem
90% Success 9822 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

We are given $$N$$ numbers. We have to select $$K$$ of them. We also have a number $$M$$. Suppose the numbers we selected were $$A_1, A_2 , A_3 .. A_k$$. (note that we write these numbers in order in which they appeared in the original array). Define $$ S = \sum_{i = 1}^{k}{A_i \cdot  (i \mod M) } $$.
We have to maximize $$ S $$.

Constraints : 

 $$ N \leq 10^4 $$
 $$ K \leq 10^3 $$
 $$ | A_i | \leq 10^7 $$
 $$ M \leq 10^7 $$

Input Format : 

 In the first line, three space separated integers $$N,K,M$$ are given. In the next line, $$N$$ space separated integers $$A_1,A_2,A_3, \dots A_n$$ are given.

Output Format :

Print a single integer corresponding to the answer. 

 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
9 votes
Tags:
Dynamic ProgrammingAlgorithms2D dynamic programmingData Structures
Points:30
3 votes
Tags:
AlgorithmsApprovedDynamic ProgrammingImplementationMediumOpenProbabilityStatisticsTwo dimensional
Points:30
18 votes
Tags:
ApprovedDynamic ProgrammingMathMediumNumber TheoryOpen