Cod sursa(job #24531)

Utilizator dominoMircea Pasoi domino Data 2 martie 2007 19:50:34
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>

#define MAX_N 200005
#define FIN "buline.in"
#define FOUT "buline.out"

int N, A[MAX_N], S, P, L, sum[MAX_N], pos[MAX_N];

int main(void)
{
    int i, a, b, s, p;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d %d", &a, &b);
        A[i] = a*(b ? +1 : -1);
    }

    S = s = A[N]; P = p = N; L = 1;
    for (i = N-1; i > 0; i--)
    {
        s += A[i];
        if (s <= A[i]) s = A[i], p = i;
        if (S <= s) S = s, P = i, L = p-i+1;
    }
    for (i = 1; i <= N; i++)
        sum[i] = sum[i-1]+A[i];
    for (pos[1] = 1, i = 2; i <= N; i++)
    {
        pos[i] = pos[i-1];
        if (sum[pos[i]] < sum[i]) pos[i] = i;
    }
    for (s = 0, i = N; i > 0; i--)
    {
        s += A[i]; p = s+sum[pos[i-1]];
        if (S < p || (S == p && P > i))
            S = p, P = i, L = N-i+1+pos[i-1];
    }

    printf("%d %d %d\n", S, P, L);

    return 0;
}