Cod sursa(job #466699)

Utilizator bog29Antohi Bogdan bog29 Data 27 iunie 2010 13:28:00
Problema Numarare Scor 20
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 0.73 kb
#include<fstream>
#include<vector>
#define dmax 100004
using namespace std;
ifstream in("numarare.in");
ofstream out("numarare.out");

int n,x[dmax];
long int sol;
vector<int>g[dmax];
vector<int>::iterator it;

int bun(int a,int b)
{	for(it=g[a].begin();it<g[a].end();it++)
		if(*it==b)return 1;
	return 0;
}

int main()
{	int i,j;
	in>>n;
	for(i=1;i<=n;i++)
	{	in>>x[i];
		//sp[i]=sp[i-1]+x[i];
	}
	in.close();
	sol=n-1;
	for(i=1;i<n;i++)
		g[i].push_back(i+1);
	for(i=4;i<=n;i+=2)
		for(j=1;j<=n-i+1;j++)
		{	//out<<i<<" "<<j<<" "<<j+i-1<<'\n';
			if(x[j+i-1] + x[j] == x[j+1] + x[j+i-2])
				if(bun(j+1,j+i-2) )
				{	sol++;
					g[j].push_back(j+i-1);
				}
		}		
	out<<sol;
	out.close();
	return 0;
}