# PBinfo #3876 – sum_max_min – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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 \( {10}^{9} + 7 \).

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.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 20;
int a[MAXN];
void max_self(int &x, const int &y) {
  if (x < y)
    x = y;
}
void min_self(int &x, const int &y) {
  if (x > y)
    x = y;
}
void add_self(int &x, const int &y) {
  x += y;
  if (x >= mod)
    x -= mod;
}
int main() {
  int n, t;
  cin >> n >> t;
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  int ans = 0;
  for (int mask = 1; mask < (1 << n); ++mask) {
    int mx = -INF, mn = INF;
    for (int i = 0; (1 << i) <= mask; ++i)
      if (mask & (1 << i)) {
        max_self(mx, a[i]);
        min_self(mn, a[i]);
        if (mx - mn > t)
          break;
      }
    if (mx - mn <= t)
      add_self(ans, mx - mn);
  }
  cout << ans << '\n';
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3876)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3876/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3876/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)