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

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