Cod sursa(job #133827)

Utilizator FlorianFlorian Marcu Florian Data 9 februarie 2008 20:31:06
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<stdio.h>
#define Max 200003
FILE*f=fopen("buline.in","r");
FILE*g=fopen("buline.out","w");
long long s[Max],t[Max],a[Max],smax,inc,sf,lung;
long long n;
void read()
  {
  fscanf(f,"%lld\n",&n);
  long long i,p;
  for(i=1;i<=n;++i)
    {
    fscanf(f,"%lld %lld",&a[i],&p);
    if(p==0) a[i]=-1*a[i];
    }
  }
void ParteaI()
  {
  long long sc=0,p=1;
  sf=1;
  inc=1;
  long long i;
  smax=a[1];
  sc=a[1];
  for(i=2;i<=n;++i)
    {
    if(sc<=0)
      {
      sc=a[i];
      p=i;
      }
    else sc+=a[i];

    if(sc>smax)
        {
        smax=sc;
        inc=p;
        sf=i;
        }
    }
  lung=sf-inc+1;
  }
void ParteaII()
  {
  long long s[Max],t[Max];
  long long i,j,S,pi;
  S=smax;
  pi=inc;
  s[0]=0;
  t[0]=0;
  for(i=1;i<=n;++i)
    {
    s[i]=s[i-1]+a[i];
    t[i]=t[i-1];
    if(s[i]>t[i]) t[i]=s[i];
    }
  for(i=1;i<=n;++i)
    {
    if(t[i-1]+s[n]-s[i-1]>smax)
       {
       smax=t[i-1]+s[n]-s[i-1];
       inc=i;
       }
       
    }
  if(smax>S || inc<pi)
    {
    long long sum=0;
    lung=1;
    for(i=inc;;i=i%n+1)
      {
      sum+=a[i];
      if(sum==smax)
        {
        sf=i;
        break;
        }
      else lung++;
      }
    }
      
  }
int main()
  {
  read();
  ParteaI();
  ParteaII();
  fprintf(g,"%lld %lld %lld\n",smax, inc, lung);
  return 0;
  }