Cod sursa(job #26285)

Utilizator damaDamaschin Mihai dama Data 5 martie 2007 13:49:21
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#define nmax 400001

int v[nmax], s[nmax], st[nmax], summax = - 10001, start, len, n, sum[nmax], t[nmax];

int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    
    int i, a, b;
    
    scanf("%d", &n);
    
    for(i = 1; i <= n; ++i)
    {
		  scanf("%d%d", &a, &b);
		  if(b == 0)
		  {
			   v[i] = -a;
	   	  }
	   	  else
	   	  {
			  v[i] = a;
		  }
		  v[n + i] = v[i];
		  if(s[i - 1] > 0)
		  {
				 s[i] = s[i - 1] + v[i];
				 st[i] = st[i - 1];
 		  }
 		  else
 		  {
				 s[i] = v[i];
				 st[i] = i;
		  }
		  if(s[i] > summax || (s[i] == summax && st[i] < start) || (s[i] == summax && st[i] == start && i - st[i] + 1 < len))
		  {
				  summax = s[i];
				  start = st[i];
				  len = i - st[i] + 1;
		  }
		  sum[i] = sum[i - 1] + v[i];
		  if(sum[t[i - 1]] > sum[i])
		  {
					 t[i] = t[i - 1];
	   	  }
	   	  else
	   	  {
			  t[i] = i;
		  }
	}
	
	for(i = 2; i <= n; ++i)
	{
		  if(sum[n] - sum[i - 1] + sum[t[i - 1]] > summax || (sum[n] - sum[i - 1] + sum[t[i - 1]] == summax && i < start) || (sum[n] - sum[i - 1] + sum[t[i - 1]] == summax && i == start && n - i + 1 + t[i - 1] < len))
		  {
				  summax = sum[n] - sum[i - 1] + sum[t[i - 1]];
				  start = i;
				  len = n - i + 1 + t[i - 1];
		  }
 	}

	printf("%d %d %d\n", summax, start, len);

    return 0;
}