Cod sursa(job #929994)

Utilizator horatiu13Horatiu horatiu13 Data 27 martie 2013 13:14:29
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#define MAX 200001
#define MAX2 400002
#define inf ~(1<<31)+1


int v[MAX];
int S[MAX2];
int n;
int st;
int poz;
int uc;
int maxim=-inf;

void initializare()
{
	for(int i=0; i<=2*n; i++)
		S[i]=-inf;
}

void citire()
{
	FILE *g=fopen("buline.in", "r");
	FILE *f=fopen("buline.out", "w");
	int x;
	fscanf(g, "%d", &n);
	initializare();
	for(int i=1; i<=n; i++)
	{
		fscanf(g, "%d%d", &v[i], &x);
		if(!x)
			v[i]=-v[i];
			
		if(S[i-1]==-inf || v[i] > v[i]+S[i-1])
		{
			S[i] = v[i];
			uc=i;
			if(S[i]>maxim)
			{
				maxim=S[i];
				poz=i;
				st=uc;
			}
		}
		else
		{
			S[i] = S[i-1] + v[i];
			if(S[i]>maxim)
			{
				maxim=S[i];
				poz=i;
				st=uc;
			}
		}
			
	}
	for(int i=1; i<n; i++)
	{
		if(S[n+i-1]==-inf || v[i] > v[i]+S[n+i-1])
		{
			S[n+i] = v[i];
			uc=i;
			if(S[n+i]>maxim)
			{
				maxim=S[n+i];
				poz=n+i;
				st=uc;
			}
		}
		else
		{
			S[n+i] = S[n+i-1] + v[i];
			if(S[n+i]>maxim)
			{
				maxim=S[n+i];
				poz=n+i;
				st=uc;
			}
		}
	}
	//for(int i=1; i<2*n; i++)
		//printf("%d ", S[i]);
	fprintf(f, "%d %d %d", maxim, st, poz-st+1);
}

int main()
{
	citire();
	return 0;
}