Vizualizare sursă pentru „3876 - sum max min”


= Cerința =
Se dă un șir de <code>N</code> numere întregi. Pentru fiecare subșir nevid al șirului dat se consideră valoarea întreagă <code>D</code> egală cu diferența dintre elementul maxim și cel minim aflat în subșir. Să se afle suma valorilor <code>D</code> ale tuturor subșirurilor nevide, mai mici sau egale decât un număr întreg <code>T</code> dat modulo .

= Date de intrare =
Programul citește de la tastatură numerele <code>N</code> și <code>T</code>, iar apoi <code>N</code> numere întregi, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran valoarea cerută în enunț.

= Restricții și precizări =

* <code>1 ≤ N, T ≤ 1.000.000</code>
* cele <code>N</code> numere citite vor fi din intervalul <code>[0, 1.000.000]</code>
* se numește subșir al unui șir o succesiune de elemente(nu neapărat consecutive în acesta) ale acestuia, considerate în ordinea în care apar în șir
* pentru teste în valoare de <code>20</code> de puncte <code>N ≤ 20</code>

= Exemplu: =
Intrare
 5 2
 1 7 2 3 4
Ieșire
 11

=== Explicație ===
Dacă considerăm șirul indexat de la <code>1</code>, un exemplu de subșir ce respectă condiția din enunț este cel format din elementele de pe pozițiile <code>1</code>, <code>3</code> și <code>4</code>, <code>D</code> fiind egal în acest caz cu <code>2</code>, deci egal cu <code>T = 2</code>. Un alt subșir bun este cel format de elementele de pe pozițiile <code>3</code>, respectiv <code>4</code>, <code>D</code> fiind egal în acest caz cu <code>1</code>, deci mai mic decât <code>T = 2</code>. Subșirul format de elementele de pe pozițiile <code>2</code> și <code>3</code> nu respectă condiția din enunț pentru că în cazul acestuia <code>D = 5 > T = 2</code>. Analizând toate subșirurile se obține în final suma <code>11</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 1000000007 

def calculate_subarray_sums(n, t, numbers):
    total_sum = 0  # Initialize total sum

    for i in range(n):
        max_so_far = numbers[i]
        min_so_far = numbers[i]
        subarray_count = 1

        for j in range(i + 1, n):
            max_so_far = max(max_so_far, numbers[j])
            min_so_far = min(min_so_far, numbers[j])

            difference = max_so_far - min_so_far

            if difference <= t:
                contribution = (subarray_count * difference) % MOD

                total_sum = (total_sum + contribution) % MOD

                subarray_count += 1

    return total_sum

def main():
    n, t = map(int, input().split())
    numbers = list(map(int, input().split()))

    subarray_sum = calculate_subarray_sums(n, t, numbers)
    print(subarray_sum)

if __name__ == "__main__":
    main()

</syntaxhighlight>