Cod sursa(job #216550)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 24 octombrie 2008 20:21:23
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>

int t[200001],inceput,lungime,l[200001],s[200001],a[200001],n;
long sm,smax;
void citire()
{   int v;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     {
      scanf("%d %d",&a[i],&v);
      if(v==0)
	a[i]=a[i]*(-1);
     }
}

int max(int x,int y)
{
   if(x>y)
    return x;
    else
    return y;
}

void solve()
{

    for(int i=1;i<=n;i++)
      s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++)
      {t[i]=max(t[i-1],s[i]);
       if(t[i]==s[i])
         l[i]=i;
        else
         l[i]=l[i-1];
      }
    long ss;
    ss=0;smax=-200001;
    for(int i=1;i<=n;i++)
	{
	 ss=t[i-1]+s[n]-s[i-1];
	 if(ss>smax)
	  {smax=ss;
	   inceput=i;
	   lungime = l[i-1] + n - i + 1;
	  }
	}


}

int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    citire();
    solve();
    printf("%ld %d %d",smax,inceput,lungime);
    return 0;
}