Cod sursa(job #185769)

Utilizator Mishu91Andrei Misarca Mishu91 Data 25 aprilie 2008 23:58:28
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#define MAX_N 200000

int N,V[MAX_N],L[MAX_N];
int 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;
    int maxl=0,min = 0;
    for(i = 1; i<=N; i++)
    {
        M[i] = max((S[i] = S[i-1] + V[i]), M[i-1]);
        if(M[i] == S[i])
            L[i] = L[i-1]+1;
        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 - i + min + 1,lg = i - 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();
}