Cod sursa(job #1409262)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 30 martie 2015 14:21:35
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 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);
	for(int i=0; i<n; i++)
	{
		int x, type;
		scanf("%d%d", &x, &type);
		a[i] = a[i+n] = x * (type>0 ? 1 : -1);
	}
	int s = a[0];
	int smax = a[0];
	int st = 0, posmax = 0, lgmax = 1;
	for(int i=1; i<2*n; i++)
	{
		if(i-st+1 == n)
		{
			s-=a[st];
			st++;
		}
		if(s<0)
		{
			s = a[i];
			st = i;
		}
		else s += a[i];
		if(s > smax)
		{
			smax = s;
			posmax = st;
			lgmax = i-st+1;
		}
		else if(s == smax && lgmax > i-st+1)
		{
			posmax = st;
			lgmax = i-st+1;
		}
	}
	printf("%d %d %d", smax, posmax+1, lgmax);
    return 0;
}