Cod sursa(job #1409320)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 30 martie 2015 14:40:35
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>

using namespace std;

const int nmax = 200000;

int a[2*nmax+5];

int main()
{
    freopen("buline.in", "r", stdin);
	freopen("buline.out", "w", stdout);
	int n;
	scanf("%d", &n);
	int sum = 0;
	for(int i=0; i<n; i++)
	{
		int x, type;
		scanf("%d%d", &x, &type);
		a[i] = x * (type>0 ? 1 : -1);
		sum+=a[i];
	}
	int st = 0;
	int s = a[0];
	int smax = a[0];
	int stmax = 0;
	int drmax = 0;
	for(int i=1; i<n; i++)
	{
		if(s < 0)
		{
			s = a[i];
			st = i;
		}
		else s += a[i];
		if(s > smax)
		{
			smax = s;
			stmax = st;
			drmax = i;
		}
	}
	st = 0;
	s = a[0];
	int smin = a[0];
	int stmin = 0;
	int drmin = 0;
	for(int i=1; i<n; i++)
	{
		if(s > 0)
		{
			s = a[i];
			st = i;
		}
		else s+=a[i];
		if(s < smin)
		{
			smin = s;
			stmin = st;
			drmin = i;
		}
	}
	int sans, stans, lgans;
	if(smax > sum - smin)
	{
		sans = smax;
		stans = stmax;
		lgans = drmax - stmax + 1;
	}
	else
	{
		sans = smin;
		stans = (drmin+1)%n;
		lgans = n-(drmin - stmin + 1);
	}
	printf("%d %d %d", sans, stans+1, lgans);
    return 0;
}