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.
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
Editorial