Cod sursa(job #1538411)

Utilizator AeroHHorea Stefan AeroH Data 28 noiembrie 2015 23:07:29
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <iostream>
#include <deque>
#include <algorithm>
#include <deque>
using namespace std;

ifstream f("buline.in");
ofstream g("buline.out");

int n,i,v[400005],j,P,L,Pf,Lf,rasp,a,b,x,sum;
deque<int> d;
int main()
{
    f >> n;
    for (i = 1;i <= n; ++i)
    {
        f >> a >> b;
        x = a * (b ? 1 : -1);
        v[ i ] = v[ i + n ] = x;
        v[ i ]+= v[i - 1];
    }
    for (i = n+1;i <= 2*n; ++i)
        v[ i ] += v[i - 1];

    rasp = -(1<<20);

    for(i = 1;i <= 2*n; ++i)
    {
        while(d.size() && v[d.back()] > v[i])d.pop_back();
        d.push_back(i);
        if (i - d.front() >=n )d.pop_front();
        if (v[i] - v[d.front()] > rasp)
        {
            rasp = v[i] - v[d.front()];
            P = d.front() + 1;
            L = i - d.front();
        }
    }

    g << rasp << " " << P << " " << L <<'\n';

    return 0;
}