Cod sursa(job #166573)

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

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

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

   for (i = 1; 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;
      }
   }
   i = pi; 
   int lung = pf - pi + 1;
   while (lung--)
   {
       sum += s[i] - s[i - 1];
       i++;
       if (i > n) i = 1;
   }

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