Cod sursa(job #216554)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 24 octombrie 2008 20:39:10
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 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()
{
    int min=0;
    for(int i=1;i<=n;i++)
      {s[i]=s[i-1]+a[i];
       t[i]=max(t[i-1],s[i]);
       if(t[i]==s[i])
         l[i]=i;
        else
         l[i]=l[i-1];
       if(s[i-1] < s[min])
             min = i-1;
         if(s[i] - s[min] > smax || !inceput)
             smax = s[i] - s[min],inceput = min + 1,lungime = i - min;
       }
    long ss;
    for(int i=2;i<=n;i++)
	{
	 ss=t[i-1]+s[n]-s[i-1];
	 if(ss<smax) continue;
	 if((s[n] - s[i-1] + t[i-1] == smax) && ((i > inceput) || (l[i-1] + n - i + 1) > lungime)) continue;
	  {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;
}