Cod sursa(job #1005346)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 4 octombrie 2013 20:42:19
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

const int Nmax = 400005;

int N;
deque <int> DQ;
long long A[Nmax];
long long best, start, finish;

void read()
{
    ifstream f("buline.in");

    f >> N;

    for ( int i = 1, tip; i <= N; ++i )
    {
        f >> A[i] >> tip;

        if ( tip == 0 )
                A[i] *= ( - 1 );
        else
                A[i] = A[i];
    }

    for ( int i = N + 1; i < 2 * N; ++i )
            A[i] = A[i - N];

    for ( int i = 1; i < 2 * N; ++i )
            A[i] += A[i - 1];

    f.close();
}

void solve()
{
    for ( int i = 1; i < 2 * N; ++i )
    {
        while ( !DQ.empty() && DQ.front() <= i - N )
                DQ.pop_front();

        while ( !DQ.empty() && A[ DQ.back() ] > A[i] )
                DQ.pop_back();

        DQ.push_back( i );

        if ( A[i] - A[ DQ.front() ] > best )
        {
            best = A[i] - A[ DQ.front() ];
            start = DQ.front() + 1;
            finish = i - DQ.front();
        }
    }
}

void print()
{
    ofstream g("buline.out");

    g << best << " " << start << " " << finish << "\n";

    g.close();
}

int main()
{
    read();
    solve();
    print();

    return 0;
}