Cod sursa(job #961085)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 16:56:32
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
 
#define MAXN 400005
 
int N, x[MAXN], s[MAXN], bst[MAXN], bstp[MAXN];
int d[MAXN], p[MAXN], dl, dr;
 
void initdeque()
{
    dl = 0; dr = -1;
}
 
void adddeque( int val, int poz, int L )
{
    for (; dr >= dl && d[dr] >= val; dr--);
    d[ ++dr ] = val;
    p[ dr ] = poz;
    if (poz - p[dl] >= L)
        dl++;
}
 
int main()
{
    freopen("buline.in", "rt", stdin);
    freopen("buline.out", "wt", stdout);
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
    {
        int val, t;
        scanf("%d %d", &val, &t);
        if (t == 0)
            x[i] = -val;
        else
            x[i] = val;
        s[i] = s[i - 1] + x[i];
    }
 
    for (int i = N + 1; i < N + N; i++)
        x[i] = x[i - N],
        s[i] = s[i - 1] + x[i];
 
    initdeque();
    adddeque( s[0], 0, N );
    int MAX = -0x3f3f3f3f, MAXi = -1;
    for (int i = 1; i < N + N; i++)
    {
        bst[i] = s[i] - d[dl];
        bstp[i] = p[dl];
 
        adddeque( s[i], i, N );
        if (bst[i] > MAX)
        {
            MAX = bst[i];
            MAXi = i;
        }
    }
 
    printf("%d %d %d\n", MAX, bstp[MAXi] + 1, MAXi - bstp[MAXi]);
 
    return 0;
}