Cod sursa(job #2673349)

Utilizator victorzarzuZarzu Victor victorzarzu Data 16 noiembrie 2020 16:34:20
Problema Numarare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 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; 
      rez += k;
      if(i + k > r)
        {
          l = i - k;
          r = i + k;
        }
    }
}
 
int main()
{
  Read();
  Solve();
  return 0;
}