Pagini recente » Cod sursa (job #976676) | Cod sursa (job #1628845) | Autentificare | Cod sursa (job #2135008) | Cod sursa (job #166569)
Cod sursa(job #166569)
//buline - IA
#include <stdio.h>
int n, a, b, s[400004], deque[400004], qbegin, qend, max = -10001;
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;
}