Cod sursa(job #2673342)

Utilizator victorzarzuZarzu Victor victorzarzu Data 16 noiembrie 2020 16:28:44
Problema Numarare Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("numarare.in");
ofstream g("numarare.out");
int s[100005], d[100005], n, x, y;
long long rez;

void Read()
{
  f>>n;
  f>>x;
  for(int i = 1;i < n;++i)
    f>>y, s[i] = abs(x - y), x = y;
} 

void Solve()
{
  int l = 1, r = -1, k;
  for(int i = 1;i < n;++i)
    {
      k = (i > r) ? 1 : min(d[l + r - i], r - i + 1); //ca sa porneasta de la pozitia viitoare
      while(1 <= i - k && i + k <= n && s[i - k] == s[i + k])
        ++k;
      d[i] = k; 
      --k; //ca a ajuns la o pozitie care nu e buna
      if(i + k > r)
        {
          l = i - k;
          r = i + k;
        }
    }
  for(int i = 1;i < n;++i)
    rez += d[i];
  g<<rez;
}

int main()
{
  Read();
  Solve();
  return 0;
}