Cod sursa(job #216522)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 24 octombrie 2008 19:46:28
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>

int t[20001],smax,sm,inceput,lgmax,s[2000],n;

void citire(int a[20001])
{   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 a[20001])
{

    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]);
    int ss;
    ss=0;smax=-20001;
    for(int i=1;i<=n;i++)
	{
	 ss=t[i-1]+s[n]-s[i-1];
	 if(ss>smax)
	  {smax=ss;
	   inceput=i;
	  }
	}
   ss=a[inceput-1];sm=-10000;
   int lg=1;
   for(int i=inceput-2;i!=inceput;i--)
     {
      if(i==0) i=n;
      if(ss<=0)
        {ss=a[i];
         lg=1;
        }
        else
         {ss=ss+a[i];
          lg++;
         }
      if(ss>sm)
       {sm=ss;
        lgmax=lg;
       }
     }

}

int main()
{
    int a[20001];
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    citire(a);
    solve(a);
    printf("%d %d %d",smax,inceput,lgmax+1);
    return 0;
}