Cod sursa(job #25474)

Utilizator rusRus Sergiu rus Data 4 martie 2007 12:41:37
Problema Buline Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasa a 9-a si gimnaziu Marime 1.76 kb
#include<stdio.h>
#define dim 2000002
int a[dim];
int n;
int max,poz;
int x[dim],y[dim];
int i,j,i1=1;
int smax,pozinceput,pozsf;
int sumarosii,sumanegre;
void citire();
void dinamica();
void afisare();
void solve();

int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    
    citire();
    solve();    
    dinamica();
    afisare();
    return 0;
}
void citire()
{
     scanf("%d",&n);
     for(i=1;i<=n;i++)
          scanf("%d %d",&x[i],&y[i]);
}
void solve()
{
     max=-32000;
     
     for(i=1;i<=n;i++)
     {
                      if(y[i]==0)
                      sumanegre+=x[i];
                      else
                      sumarosii+=x[i];
     }
    
     if(sumarosii>sumanegre)
         poz=1;
           else
          poz=0;
     
     for(i=1;i<=n;i++)
      a[i]=i;
      for(i=n+1;i<=(2*n-1);i++)
       a[i]=i-n;
      for(i=1;i<=(2*n-1);i++)
        
         if(y[i]==0 && poz==1)

	 a[i]=-x[i];
	 else

	 a[i]=x[i];

       for(i=1;i<=(2*n-1);i++)
       
       if(poz==0)
       if(y[i]==1)
	
	  a[i]=-x[i];
	  else
          a[i]=x[i];
      for(i=n+1;i<=(2*n)-1;i++)
	  a[i]=a[i-n];
      

       

}
void dinamica()
{
     int s=0,i;
     
     
     for(i=1;i<=(2*n-1);i++)
      if(a[i]+s>smax)
      {
                     s+=a[i];
                     smax=s;
                     i1=i1;
                     pozsf=i;
                     //if(pozsf>n) break;
      }
      else
          if(a[i]+s>0)
           s+=a[i];
           else
           {
               s=0;
               i1=i+1;
               
           }
}
               
void afisare()
{
     printf("%d %d %d",smax,i1,pozsf-i1+1);
     
}