Cod sursa(job #2946481)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 24 noiembrie 2022 21:44:58
Problema Numarare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>

using namespace std;
ifstream f("numarare.in");
ofstream g("numarare.out");
int n,a[200001],x,y,i,j,l,r,b[200001];
long long s;
int main()
{
    f>>n;
    int oo=99999999;
    a[1]=a[0]=oo;
    for(int i=2;i<=2*n+1;i++)
    {
        f>>a[i];
        a[++i]=oo;
    }
    int l=3,r=3;
    for(int i=3;i<=2*n;i+=2)
    {

        a[i]=a[i-1]+a[i+1];
        b[i]=max(1,min(r-i,b[l+r-i]));
        while(a[i+b[i]]+a[i-b[i]]==a[i])
            b[i]+=2;
        if(i+b[i]>r)
            r=i+b[i],l=i-b[i];
        s=s+(b[i]-1)/2;
    }
    g<<s;
    return 0;
}