Cod sursa(job #1558383)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 29 decembrie 2015 00:45:43
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#define NM 400005

using namespace std;

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

int n, i, j, p;
int v[NM], semn;
int be, en, l;
long long s[NM], minim;
long long nr[NM], mx;

int main()
{
    fin >> n;
    mx=-50000000000;
    for (i=1; i<=2*n; i++)
    {
        if (i<=n)
        {
            fin >> v[i] >> semn;
            if (semn==0)
              v[i]=-v[i];
        }
        else
          v[i]=v[i-n];
        s[i]=s[i-1]+v[i];
        if (i>n && be<=en && i-nr[be]+1>n)
          be++;
        if (s[i]-s[nr[be]]>mx)
        {
            p=nr[be]+1;
            l=i-nr[be];
            mx=s[i]-s[nr[be]];
        }
        while (s[i]<s[nr[en]] && en>=be)
          en--;
        en++;
        nr[en]=i;
    }
    fout << mx << " " << p << " " << l;
    fin.close();
    fout.close();
    return 0;
}