Cod sursa(job #882431)

Utilizator misinozzz zzz misino Data 19 februarie 2013 08:52:02
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,i,b,a,s,smax,s1,smax1,st,pi,pi1,pb,pb1,pe,pe1,v[220000];
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>a>>b;
        if(b==0)
        b=-1;
        v[i]=a*b;
        st+=a*b;
    }
    s=smax=s1=smax=-(1LL<<31);
    for(i=1;i<=n;++i)
    {
        if(s<0)
        {
            s=0,pi=i;
        }
        if(s1<0)
        {
            s1=0,pi1=i;
        }
        s+=v[i];
        s1+=-v[i];
        if(s>smax)
        {
            smax=s;
            pb=pi;
            pe=i;
        }
        if(s1>smax1)
        {
            smax1=s1;
            pb1=pi1;
            pe1=i;
        }
    }
    st+=smax1;
    if(st>smax)
    {
        smax=st;
        pb=pe1+1;
        pe=pb1-1+n;
    }
    g<<smax<<' '<<pb<<' '<<pe-pb+1<<'\n';
    return 0;
}