Cod sursa(job #2761011)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 30 iunie 2021 02:33:48
Problema Numarare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("numarare.in");
ofstream fout ("numarare.out");

int n, v[100002], p[100002];
long long ans;


int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++)
    fin >> v[i];
  for (int i = 1; i < n; i++)
    v[i] = v[i + 1] - v[i];
  int l = 0, r = 0;
  int t = 0;
  for (int i = 1; i < n; i++) {
    if (i > r)
      t = 0;
    else
      t = min(r - i, p[l + r - i]);
    while (i + t < n && v[i - t] == v[i + t])
      t++;
    p[i] = t;
    if (i + t > r) {
      l = i - t;
      r = i + t;
    }
    ans += t;
  }
  fout << ans;
  return 0;
}