Cod sursa(job #1558356)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 29 decembrie 2015 00:23:04
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 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>l)
          be++;
        for (j=en; j>=be; j--)
        {
           // fout << s[i] << " " << s[nr[j]] << '\n';
            if (s[i]-s[nr[j]]>mx)
            {
                p=nr[j]+1;
                l=i-nr[j];
                mx=s[i]-s[nr[j]];
            }
        }
        while (en>be+1 && s[i]<=s[nr[en]])
          en--;
        en++;
        nr[en]=i;
    }
    fout << mx << " " << p << " " << l;
    fin.close();
    fout.close();
    return 0;
}