Cod sursa(job #1640428)

Utilizator DysKodeTurturica Razvan DysKode Data 8 martie 2016 17:27:39
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <deque>

using namespace std;

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

int v[400010],i,j,n,m,ans,sum,l,r;
deque <int> d;

int main()
{
    ans = -100000;
    fin>>n;
    for( i = 1 ; i <= n ; i++ )
    {
        fin>>v[ i ]>>l;
        if( !l )
            v[ i ] *= -1;
        v[ i + n ] = v[ i ];
    }

    for( i = 1 ; i <= 2*n ; i++ )
        v[ i ] += v[ i - 1 ];
    d.push_back( 0 );
    ans = -100000;
    for( i = 1 ; i <= 2 * n ; i++ )
    {
        if( v[ i ] - v[ d.front() ] > ans )
        {
            ans = v[ i ] - v[ d.front() ];
            l = d.front() + 1;
            r = i-l+1;
        }
        while( d.size() && v[ d.back() ] >= v[ i ] )
            d.pop_back();
        d.push_back( i );
        if( d.front() == i - n + 1 )
            d.pop_front();
    }

    fout<<ans<<' '<<((l>n)?l-n:l)<<' '<<((r>n)?r-n:r);
return 0;
}