3876 - sum max min

Cerința

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

Date de intrare

Programul citește de la tastatură numerele N și T, iar apoi N 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

• 1 ≤ N, T ≤ 1.000.000
• cele N numere citite vor fi din intervalul [0, 1.000.000]
• 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 20 de puncte N ≤ 20

Exemplu:

Intrare

5 2
1 7 2 3 4

Ieșire

11

Explicație

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

Rezolvare

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()