Cod sursa(job #166568)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 28 martie 2008 08:26:33
Problema Buline Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
//buline - IA
#include <stdio.h>
int n, a, b, s[400004], deque[400004], qbegin, qend, max;

int main()
{
   freopen("buline.in","r",stdin);
   freopen("buline.out","w",stdout);

   int i, pi, pf;
   scanf("%d",&n);
   for (i = 1; i <= n; i++)
   {
      scanf("%d %d",&s[i], &a);
      if (!a) s[i] *= (-1);
      s[i + n] = s[i];
   }

   for (i = 2; i <= 2 * n; i++) s[i] = s[i - 1] + s[i];

   qbegin = 1;

   for (i = 1; i <= 2 * n; i++)
   {
      qend++;
      while (qend > qbegin && s[deque[qend-1]] > s[i - a]) qend--;
      deque[qend] = i - 1;

      if (deque[qbegin] < i - n) qbegin++;

      if (s[i] - s[deque[qbegin]] > max)
      {
	max = s[i] - s[deque[qbegin]];
	pi = deque[qbegin]+1;
	pf = i;
      }
   }

   printf("%d %d %d\n",max,pi,pf -  pi + 1);
   return 0;
}