Cod sursa(job #27109)

Utilizator RutZapGruia Radu RutZap Data 6 martie 2007 09:13:48
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
int n,s,smax,smin;
int huge v[200000];


int main()
{
 freopen("buline.in","r", stdin);
 freopen("buline.out","w", stdout);
 int i,j,a,b,af,bf,af2,bf2,stot=0;

 scanf("%d",&n);
 for (i=1;i<=n;i++)
  {
   scanf("%d %d", &a, &b);
   if (b==0) b=-1;
   v[i]=a*b;
  }

 s=smax=-32000;

 for (i=1;i<=n;i++)
  {
  stot+=v[i];
   if (v[i] > v[i]+s) {s=v[i];a=i;b=1;}
     else {s+=v[i];b++;}

   if (s>smax) {
		smax=s;
		af=a;bf=b;
	       }

  }


 s=smin=32000;

 for (i=1;i<=n;i++)
  {
   if (v[i] < v[i]+s) {s=v[i];a=i;b=1;}
     else {s+=v[i];b++;}

   if (s<smin) {
		smin=s;
		af2=a;bf2=b;
	       }

  }

 smin=stot-smin;

 if (smin>smax) {smax=smin;af=(af2+bf2)%n;bf=n-bf2;}

 printf ("%d %d %d", smax, af, bf);

 return 0;
}