Fişierul intrare/ieşire:subpermutari.in, subpermutari.outSursăONIS 2016 Runda Online
AutorEugenie Daniel PosdarascuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subpermutari

Fie P o permutare de lungime N. Spunem ca o alta permutare R (de lungime M ≤ N) este o subpermutare a lui P pe pozitia i ( i ≤ N - M + 1 ) daca oricare ar fi j si k intre 1 si M cu j ≠ k si R[j] < R[k] atunci P[j + i - 1] < P[k + i - 1].
De exemplu permutarea 1 2 este o subpermutare a lui 1 3 2 4 pe pozitiile 1 si 3.

Voua vi se da o permutare P si vi se cere pentru fiecare permutare R care apare cel putin o data ca subpermutare in P să-i contorizaţi frecvenţa apariţiilor în P. Pentru simplititate vi se cere suma patratelor acestor numere.

Date de intrare

Fişierul de intrare subpermutari.in va contine pe prima linie N, marimea permutarii P.
Urmatorul rand va contine N valori distincte intre 1 si N, separate prin spatiu, elementele permutarii.

Date de ieşire

În fişierul de ieşire subpermutari.out trebuie sa se afle un singur număr, cel cerut in cerinta problemei.

Restricţii

  • 1 ≤ N ≤ 2000

Exemplu

subpermutari.insubpermutari.out
4
1 3 2 4
24

Explicaţie

Urmatoarele subpermutari apar in P:

  • 1 -> pe pozitiile 1 2 3 si 4
  • 1 2 -> pe pozitiile 1 si 3
  • 2 1 -> pe pozitia 2
  • 1 3 2 -> pe pozitia 1
  • 2 1 3 -> pe pozitia 2
  • 1 3 2 4 -> pe pozitia 1

Numarul de aparitii la aceste subpermutari este 4, 2, 1, 1, 1 si 1.
Raspunsul este 4 * 4 + 2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 + 1 * 1 = 24.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?