Cod sursa(job #393416)

Utilizator bora_marianBora marian bora_marian Data 9 februarie 2010 14:07:26
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>
using namespace std;
int v[400005];
int n,nr;
long long istart,istop,summax;
void SSm(int st,int dr);
ofstream fout("buline.out");
int main()
{
    ifstream fin("buline.in");
    ofstream fout("buline.out");
    fin>>n;
    int i;
    for(i=1;i<=n;i++)
     {
         int a,b;
         fin>>a>>b;
         if(b==0)
          v[++nr]=-a;
         else
          v[++nr]=a;
    }
    for(i=1;i<n;i++)
       v[++nr]=v[i];
   int ic,ist;
   //for(i=1;i<=nr;i++)
     // fout<<v[i];
   //fout<<endl;   
   long long sumat=0;
   for(i=1;i<=n;i++)
     {
       SSm(i,n+i-1);
     //  fout<<summax<<istart<<" ";
       if(sumat<summax)
        sumat=summax,ic=istart,ist=istop;
        }
  fout<<sumat<<" "<<ic<<" "<<ist-ic+1;
  return 0;
}                          
 void SSm(int st,int dr)  
  { 
   int sum=0,index=0;
   summax=-100000;
   sum=v[st];
   istart=st;
   istop=st;
   index=st;
   int i;
   for(i=st+1;i<=dr;i++)
   {
     if(sum<0)
      sum=v[i],index=i;
     else
      sum+=v[i];
     if(sum>summax)
      summax=sum,istart=index,istop=i;
   }
//fout<<summax<<" "<<istart<<endl;
}