Consecutive Sum (Codeforces 1733A)
Tags: Greedy, sortings

You are given an array $$$a$$$ with $$$n$$$ integers. You can perform the following operation at most $$$k$$$ times:  Choose two indices $$$i$$$ and $$$j$$$, in which $$$i \,\bmod\, k = j \,\bmod\, k$$$ ($$$1 \le i < j \le n$$$).  Swap $$$a_i$$$ and $$$a_j$$$. After performing all operations, you have to select $$$k$$$ consecutive elements, and the sum of the $$$k$$$ elements becomes your score. Find the maximum score you can get.Here $$$x \bmod y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 600$$$) — the number of test cases.Each test case consists of two lines. The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the length of the array and the number in the statement above.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)  — the array itself.

Output: For each test case, print the maximum score you can get, one per line.

Note: In the first test case, we can get a score of $$$11$$$ if we select $$$a_1, a_2$$$ without performing any operations.In the third test case, we can get a score of $$$15$$$ if we first swap $$$a_1$$$ with $$$a_4$$$ and then select $$$a_3, a_4, a_5$$$. 

Sample Inputs:
5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997

Sample Outputs:
11
7
15
10
2999999997

Solution (Python):
""""""

def i():
    (n, k) = map(int, input().split())
    s = list(map(int, input().split()))
    if k == 1:
        return str(max(s))
    c = [0] * k
    p = 1
    for x in range(n):
        if c[p] < s[x]:
            c[p] = s[x]
        p += 1
        if p == k:
            p = 0
    return str(sum(c))
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    max_indices = []
    for i in range(k):
        max_index = i
        for j in range(i + k, n, k):
            if arr[j] > arr[max_index]:
                max_index = j
        max_indices.append(max_index)
    max_sum = 0
    for index in max_indices:
        max_sum += arr[index]
    print(max_sum)

Solution (Python):
def solve(a, k):
    max_values = [0] * k
    for i in range(len(a)):
        max_values[i % k] = max(max_values[i % k], a[i])
    return sum(max_values)
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    result = solve(a, k)
    print(result)