Cod sursa(job #2673352)

Utilizator victorzarzuZarzu Victor victorzarzu Data 16 noiembrie 2020 16:36:38
Problema Numarare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 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] = y - x, 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 += d[i]; 
      if(i + k > r)
        {
          l = i - k;
          r = i + k;
        }
    }
  g<<rez;
}
 
int main()
{
  Read();
  Solve();
  return 0;
}