2358 - castig

Enunț

Ana şi Bogdan au participat la un concurs şi au obţinut premiul I, respectiv premiul al II-lea. La concurs există n premii, numerotate de la 1 la n, în ordinea în care sunt aşezate pe masă. Regulamentul concursului prevede că fiecare câştigător trebuie să aleagă exact k premii aşezate pe poziţii consecutive. Fiindcă Ana are premiul I, ea poate să îşi aleagă prima premiile. Apoi Bogdan va alege şi el k premii aşezate pe poziţii consecutive dintre cele rămase după ce a ales Ana. Ana este foarte supărată pe Bogdan, aşa că ea urmăreşte ca Bogdan să câştige cât mai puţin, fără să o intereseze prea mult ce premii alege ea.

Cerința

Scrieţi un program care, cunoscând n, k şi valorile celor n premii, determină cel mai mic număr valmin, astfel încât Bogdan să nu poate selecta k premii aşezate pe poziţii consecutive cu o valoare totală mai mare decât valmin.

Date de intrare

Fișierul de intrare castigin.txt conţine pe prima linie două numere naturale n k, reprezentând numărul total de premii şi respectiv numărul de premii consecutive pe care câştigătorii trebuie să le aleagă. Pe a doua linie se află n numere naturale v[1], v[2], …, v[n] reprezentând, în ordinea aşezării pe masă, valorile celor n premii.

Date de ieșire

Fișierul de ieșire castigout.txt va conţine o singură linie pe care va fi scris numărul natural valmin, determinat conform cerinţei.

Restricții și precizări

• 3 ≤ n ≤ 100 000
• 1 ≤ k ≤ n/3
• 1 ≤ v[i] ≤ 1 000 000 000, pentru 1 ≤ i ≤ n

Exemplu:

castigin.txt

10 3

2 5 7 3 1 22 7 2 9 1

castigout.txt

15

Explicație

Dacă Ana alege premiile cu valorile 1 22 7, secvenţa cea mai convenabilă pentru Bogdan este 5 7 3 (deci valmin este 15). Există şi alte alegeri bune pentru Ana (22 7 2), dar valmin rămâne acelaşi.

Rezolvare

def este_input_valid(n, k, v):
    if not (3 <= n <= 100000):
        return False

    if not (1 <= k <= n // 3):
        return False

    for i in range(n):
        if not (1 <= v[i] <= 1000000000):
            return False

    return True

def gaseste_valoarea_minima():
    nmax = 100002

    fin = open("castigin.txt", "r")
    fout = open("castigout.txt", "w")

    n, k = map(int, fin.readline().split())
    v = list(map(int, fin.readline().split()))

    if not este_input_valid(n, k, v):
        print("Input invalid. Verificați condițiile.")
        return

    s = [0] * nmax
    smax = [0] * nmax
    dmax = [0] * nmax

    suma_val = sum(v[:k])
    s[0] = smax[0] = suma_val

    for i in range(1, n - k + 1):
        s[i] = s[i - 1] - v[i - 1] + v[i + k - 1]
        smax[i] = smax[i - 1] if s[i] <= smax[i - 1] else s[i]

    dmax[n - k] = s[n - k]

    for i in range(n - k - 1, 0, -1):
        dmax[i] = dmax[i + 1] if s[i] <= dmax[i + 1] else s[i]

    valmin = dmax[k + 1]

    for i in range(2, k + 1):
        if valmin > dmax[i + k]:
            valmin = dmax[i + k]

    for i in range(k + 1, n - k + 1):
        maxim = smax[i - k] if smax[i - k] > dmax[i + k] else dmax[i + k]
        if maxim < valmin:
            valmin = maxim

    fout.write(str(valmin) + '\n')

    fin.close()
    fout.close()

if __name__ == "__main__":
    gaseste_valoarea_minima()