Cod sursa(job #1537033)

Utilizator DysKodeTurturica Razvan DysKode Data 26 noiembrie 2015 21:04:03
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 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;

int main()
{
    fin>>n;
    for( i = 1 ; i <= n ; i++ )
    {
        fin>>v[ i ];
        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+1<<' '<<l;

return 0;
}