Mai intai trebuie sa te autentifici.

Cod sursa(job #2156440)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 8 martie 2018 18:47:43
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>

using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

int N;
int a[400001];
int lg[400001];
int bestsecv,bestlg;
int st,dr;

void Read()
{
  fin>>N;

  bool semn;
  int best;

  fin>>a[1]>>semn;
  if(semn==0) a[1]=-a[1];
  a[N+1]=a[1];

  best=a[1];
  lg[1]=1;

  N*=2;

  for(int i=2; i<=N; ++i)
  {
    if(i<=N)
    {
      fin>>a[i]>>semn;
      if(semn==0) a[i]=-a[i];
      a[i+N/2]=a[i];
    }

    if(lg[i-1]==N/2)
    {
      best-=a[i-N/2];
      lg[i]=-1;
    }

    if(best+a[i]>a[i])
    {
      best+=a[i];
      lg[i]+=lg[i-1]+1;
    }
    else
    {
      best=a[i];
      lg[i]=1;
    }

    if(best>bestsecv)
    {
      bestsecv=best;
      bestlg=lg[i];
      dr=i;
      st=dr-lg[i]+1;
    }
  }
}

void Print()
{
  if(st>N) st-=N;

  fout<<bestsecv<<' '<<st<<' '<<bestlg<<'\n';
}

void Test()
{
  for(int i=1; i<=N; ++i)
    fout<<a[i]<<' ';

  fout<<'\n';
  for(int i=1; i<=N; ++i)
    fout<<lg[i]<<' ';
}

int main()
{
    Read();
    //Test();
    Print();

    return 0;
}