Cod sursa(job #73204)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 17 iulie 2007 13:15:36
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream.h>
long a[400000],x,y,N,S,in,lg,max=-10211431,b[400000],c[400000],d[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,max2=-1463214;
for (long q=0;q<N;q++)
{    S1+=a[q];
     b[q]=S1;
     if (b[q]>max2) {
	 for (long f=q;f<N;f++){
	     c[f]=b[q];
	     d[f]=q;}
       max2=b[q];}
     }
long lg1=0,sf=0;
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;}}
in=sf-lg+1;
if (c[N-lg-1]>0){
    max+=c[N-lg-1];
    lg+=d[N-lg-1];}
}
int main(){
ofstream fout("buline.out");
citire();
maxim();
 fout<<max<<" "<<in+1<<" "<<lg<<"\n";
fout.close();
return 0;
}