Editing 4201 - Sume Cuantice


= Introducere =
Prietenul vostru Turing vă cere din nou ajutorul! Acesta își dorește un calculator cuantic pentru a calcula o sumă colosală, imposibilă pentru orice om. Momentan nu dispune de resursele materiale și financiare pentru a lucra la nivel cuantic, așa că vă cere ajutorul!

= Cerința =
Se dă un șir cu <code>N</code> elemente, numere naturale și un număr natural <code>K</code>. Aveți la dispoziție următoarea operație care se poate folosi de maximum <code>K</code> ori: se aleg doi indici <code>i</code> si <code>j</code> pentru care <code>i % k = j % k</code> (<code>1 ≤ i < j ≤ N</code>) și se interschimbă valorile acestor doi indici.

La final, după toate operațiile, trebuie să alegeți <code>K</code> elemente consecutive, iar suma acestor <code>K</code> elemente reprezinta scorul vostru. Turing trebuie sa obtina suma maximă și vă roagă să-l ajutați!

= Date de intrare =
Prima linie contine un numar <code>T</code>, reprezentand numarul de teste. Fiecare test contine două linii.

Prima linie conține numerele <code>N</code> și <code>K</code> (<code>1 ≤ K ≤ N ≤ 1000</code>), <code>N</code> fiind numărul de elemente al șirului și <code>K</code> numărul prezentat în cerință.

A doua linie conține <code>N</code> numere întregi <code>A<sub>1</sub></code>, <code>A<sub>2</sub></code>, … , <code>A<sub>n</sub></code> ( <code>0 ≤ A<sub>i</sub></code> <code>≤ 1000</code> ), șirul de <code>N</code> numere naturale.

= Date de ieșire =
Programul va afișa pe câte un rând nou suma maximă pentru fiecare dintre cele <code>T</code> operații.

= Restricții și precizări =

* <code>1 ≤ T ≤ 1000</code>
* <code>1 ≤ K ≤ N ≤ 1000</code>
* <code>0 ≤ A[i] ≤ 1000</code>

= Exemplu: =
'''Intrare'''
 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
'''Ieșire'''
 11
 7
 15
 10
 2999999997

=== Explicație ===
În primul caz, putem obține suma maximă <code>11</code> dacă alegem <code>A<sub>1</sub></code>, <code>A<sub>2</sub></code> fără să efectuăm nicio operație.

În al treilea caz, putem obține suma maximă <code>15</code> dacă interschimbăm <code>A<sub>1</sub></code> cu <code>A<sub>4</sub></code>, iar suma finală este alcatuită din elementele <code>A<sub>3</sub></code>, <code>A<sub>4</sub></code>, <code>A<sub>5</sub></code>.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
def sume():
import sys
T, N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
B = [0] * K
for i in range(1, N+1):
    B[i % K] = max(B[i % K], A[i])
ans = sum(B)
print(ans)

</syntaxhighlight>