Cod sursa(job #744040)

Utilizator theep0Cruceru Radu theep0 Data 7 mai 2012 01:01:10
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>


int N,*vec,*dp,i,*path,S,idx;

int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d",&N);
	vec = new int[2*N];
	dp = new int[2*N];
	path = new int[2*N];
	for(i=0; i<N; ++i)
	{
		scanf("%d %d",&idx,&S);
		if(S == 0)
			vec[i] = -idx;
		else
			vec[i] = idx;
		dp[i] = vec[i];
	}
	for(i=0;i<N;++i)
	{
		vec[i+N] = vec[i];
	}
	for(i=1; i<2*N; ++i)
	{
		S = dp[i-1] + vec[i];
		if(S > dp[i] && path[i-1] < N)
		{
			dp[i] = S;
			path[i] = path[i-1]+1;
		}
	}
	S = -11111;
	idx = 0;
	for(i=0;i<2*N;++i)
	{
		if(dp[i] > S)
		{
			S = dp[i];
			idx = i;
		}
	}
	/*printf("Suma maxima: %d\nCu: ",S);
	for(i=idx;i>0;--i)
	{
		printf("%d ",vec[i]);
	}*/
	printf("%d %d %d",S,path[idx+1], (idx+path[idx+1]-1)%N);
	/*
	for(i=0; i<2*N; ++i)
		printf("%d ",path[i]);
	*/
	return 0;
}