Cod sursa(job #793482)

Utilizator idomiralinIdomir Alin idomiralin Data 3 octombrie 2012 00:48:47
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
# include <cstdio>

using namespace std;

int n, i, val, op, maxim, st, dr, front, back, a[400005], s[400005], deque[400005];
int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    
    scanf("%d",&n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d%d",&val,&op);
        a[i] = (op ? val : - val);
        a[i + n] = a[i];
        }
        
    for (i = 1; i <= 2 * n; i++)
        s[i] = s[i - 1] + a[i];
        
    
    maxim = s[n]; st = 1; dr = n; front = 1; back = 0;
    for (i = 1; i <= 2 * n; i++)
    {
        while (front <= back && s[i] < s[deque[back]]) back--;
        
        deque[++back] = i;
        
        if (deque[front] == i - n) front++;
        
        if (maxim < s[i] - s[deque[front]])
        {
                  maxim = s[i] - s[deque[front]];
                  st = deque[front] + 1;
                  dr = i;
                  }
        }
        
    printf("%d %d %d", maxim, st, dr - st + 1);
    
return 0;
}