Cod sursa(job #664703)

Utilizator s8ko14romario s8ko14 Data 20 ianuarie 2012 17:52:45
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.62 kb
#include<stdio.h>
int n,in_max,ridicare,s=0,ok=0,ok2=0,ok3=0,smax=-1;
struct fruct
{
	int inaltime;
	int greutate;
};
fruct a[100000],copie[100000],b[100000];

int back(int k)
{
	for(int i=0;i<n;i++)
		if(copie[i].inaltime>0)
		{
			ok2=0;
			b[k].inaltime=copie[i].inaltime; b[k].greutate=copie[i].greutate;
			for(int j=0;j<=k;j++)//bun
				if(b[j].inaltime+ridicare==b[k].inaltime && b[j].greutate==b[k].greutate)
				{	ok2=1; break; }
			ok=0;
			if(ok2==0)//daca este bun
			{	
				for(int j=0;j<n;j++)//ridic gutile
				{
					if(copie[j].inaltime!=-1)
						copie[j].inaltime=copie[j].inaltime+ridicare;
					if(copie[j].inaltime>in_max)
						copie[j].inaltime=-1;
				}
				for(int j=0;j<n;j++)//solutie
					if(copie[j].inaltime>0)//daca nu e solutie
					{	back(k+1); ok=1;}//ma duc in back(k+1)
				if(ok==0)//daca e solutie
				{
					for(int j=0;j<=k;j++)
						s=s+copie[j].greutate;
					for(int i=0;i<n;i++)
					{	copie[i].inaltime=a[i].inaltime; copie[i].greutate=a[i].greutate; }//reactualizez copia lui a
					for(int j=0;j<n;j++)//ridic gutile
					{
						if(copie[j].inaltime!=-1)
							copie[j].inaltime=copie[j].inaltime+ridicare*k;
						if(copie[j].inaltime>in_max)
							copie[j].inaltime=-1;
					}
					if(s>smax)
						smax=s;
				}
			}
		}
}

int main()
{
	FILE *f=fopen("gutui.in","rt");
	FILE *g=fopen("gutui.out","wt");
	fscanf(f,"%i%i%i",&n,&in_max,&ridicare);
	for(int i=0;i<n;i++)
		fscanf(f,"%i%i",&a[i].inaltime,&a[i].greutate);
	for(int i=0;i<n;i++)
	{	copie[i].inaltime=a[i].inaltime; copie[i].greutate=a[i].greutate; }
	back(0);
	fprintf(g,"%i",smax);
}