Cod sursa(job #1100163)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 6 februarie 2014 18:01:18
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>

using namespace std;

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

const int Nmax = 400100;
const int oo = 0x3f3f3f3f;

int N, V[Nmax / 2], S[Nmax], sol;
deque <int> D;

int main()
{
    fin >> N;
    for(int i = 1; i <= N; i++)
    {
        int tip;
        fin >> V[i] >> tip;
        if(!tip) V[i] = -V[i];

        S[i] = S[i - 1] + V[i];
    }

    for(int i = N + 1; i <= N + N; i++)
        S[i] = S[i - 1] + V[i - N];
    sol = S[1];
    D.push_back(1);

    int st = 1, lg = 1;
    for(int i = 2; i <= N + N; i++)
    {
        if(sol < S[i] - S[D.front()])
        {
            sol = S[i] - S[D.front()];
            st = D.front() + 1;
            lg = i - st + 1;
        }

        while(!D.empty() && S[D.back()] >= S[i])
            D.pop_back();
        D.push_back(i);

        if(D.front() <= i - N)
            D.pop_front();
    }

    fout << sol <<' ' << st << ' ' << lg;
    return 0;
}