Cod sursa(job #611887)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 4 septembrie 2011 10:25:51
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<stdio.h>
#define INF 2000000000
#define N 200001
long n,i,a[N],b,s[N],t[N],w=-INF,x,z,l,j,k,min,max;
int main()
{freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%ld",&n);
t[0]=-INF;
for(i=1;i<=n;i++)
      {scanf("%ld%ld",&a[i],&b);
      if(!b)
             a[i]=-a[i];
      if(a[i]>w)
             w=a[i],l=i;
      s[i]=a[i]+s[i-1];
      if(s[i]>t[i-1])
             t[i]=s[i];
      else
             t[i]=t[i-1];}
min=max=s[1],k=1;
for(i=2;i<=n;i++)
if(min>s[i])
      min=s[i],k=i+1;
else
      if(max<s[i])
             max=s[i];
for(j=1;j<=n;j++)
if(t[j-1]+s[n]-s[j-1]>w)
      w=t[j-1]+s[n]-s[j-1],l=j;
if(max-min>w)
      w=max-min,l=k;
for(i=l;i<n+l;i++)
      {x++;
      if(i>n)
             z+=a[i-n];
      else
             z+=a[i];
      if(z==w)
             break;}
printf("%ld %ld %ld",w,l,x);
return 0;}