Cod sursa(job #1008005)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 10 octombrie 2013 00:28:57
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#define NMAX 400400

int x[NMAX], S[NMAX], Q[NMAX];

int main()
{
    int i, N, cant, cul, p, u, now, best = (1 << 30) * (-1), X1, X2, bestX1 = 1 << 30, bestX2 = 1 << 30;

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

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d%d", &cant, &cul);
        if (cul)
            x[i] = cant;
        else
            x[i] = cant * (-1);
    }

    for (i = N + 1; i <= N + N; i++)
        x[i] = x[i - N];
    for (i = 1; i <= N + N; i++)
        S[i] = S[i - 1] + x[i];

    p = 1; u = 0;
    Q[++ u] = 0;

    for (i = 1; i <= N + N; i++)
    {
        now = S[i] - S[Q[p]];
        X1 = Q[p] + 1;
        X2 = i - Q[p];
        if ((now > best) || (best == now && X1 < bestX1) || (best == now && X1 == bestX1 && X2 < bestX2))
            best = now, bestX1 = X1, bestX2 = X2;
        while (p <= u && S[i] <= S[Q[u]])
            u --;
        Q[++ u] = i;

        if (Q[p] + N == i)
            p ++;
    }

    printf("%d %d %d", best, bestX1, bestX2);
    return 0;
}