Cod sursa(job #1537039)

Utilizator DysKodeTurturica Razvan DysKode Data 26 noiembrie 2015 21:12:34
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <deque>

using namespace std;

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

deque<int>d;
int n,m,v[400010],i,j,k,ans,poz,st,sf,l,x;

int main()
{
    fin>>n;
    for( i = 1 ; i <= n ; i++ )
    {
        fin>>v[ i ]>>x;
        if( x == 0 )
            v[ i ] *= -1;
        v[ i + n ] = v[ i ];
    }

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

    for( i = 1 ; i < 2 * n ; i++ )
    {
        while( d.size() && v[ d.back() ] > v[ i ] )
            d.pop_back();
        d.push_back( i );

        if( d.front() == i - n )
            d.pop_front();

        if( v[ i ] - v[ d.front() ] > ans )
        {
            ans = v[ i ] - v[ d.front() ];
            poz = d.front() + 1;
            l = i - poz + 1;
        }
    }

    fout<<ans<<' '<<poz<<' '<<l;

return 0;
}