Cod sursa(job #73163)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 17 iulie 2007 10:56:35
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<fstream.h>
long a[400000],x,y,N,S,in,lg,max=-10211431,b[400000];
void citire(){
ifstream fin("buline.in");
fin>>N;
for (long i=0;i<N;i++){
    fin>>x>>y;
      if (y==0)
	 a[i]=(-1)*x;
      else
	a[i]=x; }
fin.close();
}
void maxim(){
long S1=0,max1=-1254320;
for (long c=0;c<N;c++)
{    S1+=a[c];
     b[c]=S1;
     }
     int lg1=0,sf;
for (long i=0;i<N;i++){
      if (S<0){
	 S=a[i];
	 lg1=1;}
      else{
         S+=a[i];
	  lg1++;}
   if (S>max){
     max=S;
     lg=lg1;
     sf=i;}
      lg1++;}
in=sf-lg+1;
if (lg==N)
in=0;
if (sf+1==N){
for (long h=0;h<in-1;h++)
   if (b[h]>max1){
     max1=b[h];
     sf=h;}
if (max1>0){
max+=max1;
lg+=sf; }}
}
int main(){
ofstream fout("buline.out");
citire();
maxim();
fout<<max<<" "<<in+1<<" "<<lg+1<<"\n";
fout.close();
return 0;
}