Cod sursa(job #185730)

Utilizator Mishu91Andrei Misarca Mishu91 Data 25 aprilie 2008 22:37:07
Problema Buline Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <climits>
#define MAX_N 200000

int N,V[MAX_N],T[MAX_N],L[MAX_N];
long S[MAX_N],M[MAX_N];

inline long max(long a, long b)
{
    return (a > b)? a : b;
}

void read()
{
    scanf("%d",&N);
    for(int i=1,x,y; i<=N; i++)
    {
        scanf("%d %d",&x,&y);
        V[i] = (y)? x : -x;
    }
}

void solve()
{
    int i,ps=0,lg;
    long maxl=0,min = 0;
    for(i = 1; i<=N; i++)
    {
        M[i] = max((S[i] = S[i-1] + V[i]), M[i-1]);
        if(S[i] == S[i-1] + V[i])
            T[i] = T[i-1] + 1;
        else
            T[i] = 1;
        if(M[i] == S[i])
            L[i] = T[i];
        else
            L[i] = L[i-1];
        if(S[i-1] < S[min])
            min = i-1;
        if(S[i] - S[min] > maxl || !ps)
            maxl = S[i] - S[min],ps = i - T[i] + T[min] + 1,lg = T[i] - T[min];
    }
    for(i = 2; i<=N; i++)
    {
        if(S[N] - S[i-1] + M[i-1] < maxl) continue;
        if((S[N] - S[i-1] + M[i-1] == maxl) && ((i > ps) || (L[i-1] + N - i + 1) > lg)) continue;
        maxl = S[N] - S[i-1] + M[i-1];
        ps = i;
        lg = L[i-1] + N - i + 1;
    }
    printf("%ld %d %d",maxl,ps,lg);
}

int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    read();
    solve();
}