Cod sursa(job #987985)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 21 august 2013 18:48:05
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 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;
}