Cod sursa(job #844511)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 29 decembrie 2012 13:51:18
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<cstdio>
using namespace std;
int v[400010],n,i,a,b,s,begin,end,smax,inc,sf,beginf,endf,incf,sfmax,S;
int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        if(b==0) b=-1;
        v[i]=a*b;
        S+=v[i];
    }
    s=smax=sf=sfmax=-(1<<31);
    for(i=1;i<=n;i++)
    {
        if(s<0) s=0,inc=i;
        if(sf<0) sf=0,incf=i;
        s+=v[i];
        sf+=v[i]*(-1);
        if(s>smax) {smax=s; begin=inc; end=i;}
        if(sf>sfmax) {sfmax=sf; beginf=incf; endf=i;}
    }
    sf=S+sfmax;
    if(sf>smax) {smax=sf; begin=endf+1; end=beginf-1+n;}
    printf("%d %d %d\n",smax,begin,end-begin+1);
    return 0;
}