Cod sursa(job #1065138)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 22 decembrie 2013 20:32:44
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <functional>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
 int n,v[400005],s[400005],sign,d[400005],st,k=1,smax,l,lmin,sact,lact,lenact;
int main()
{ int i;
   f>>n;
  for(i=1;i<=n;i++)
   {f>>v[i]>>sign;
    if (!sign) v[i]*=-1;
   }

  for(i=n+1;i<=2*n;i++)
   v[i]=v[i-n];

   n*=2;

    k=1; d[1]=1; smax=v[1]; l=1; lmin=1;
      st=1;
     s[0]=0;
     for(i=1;i<=n;i++)
      s[i]=s[i-1]+v[i];

    for(i=2;i<=n;i++)
    {  while(st<k && i-d[st]>(n/2))
         {st++; }

      //if (s[i]<0) cout<<" ";
        //cout<<s[i]-s[d[st]]<<" ";
         sact=s[i]-s[d[st]];
       lact=(d[st]+1)%(n/2); if (!lact) lact=(n/2);
       lenact=i-d[st];
      if (sact>smax || (sact==smax && lact<l) || (sact==smax && lact==l && lenact<lmin))
        { smax=sact;
          l=lact; lmin=lenact;
        }

      while(k>=st && s[d[k]]>=s[i])
       k--;
      k++; d[k]=i;
    }

    g<<smax<<" "<<l<<" "<<lmin;
    return 0;
}