Cod sursa(job #612175)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 6 septembrie 2011 12:42:33
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <deque>
using namespace std;

int a[200010], v[400010], n, cit, sol = -2000000000, start, finish;
deque <int> deq;
int main()
{
    ifstream f("buline.in");
    ofstream g("buline.out");

    f >> n;
    for (int i = 1; i <= n; ++i)
    {
        f >> a[i] >> cit;
        a[i] = a[i] * (cit > 0 ? -1 : 1);
        v[i] = v[i - 1] + a[i];
    }

    for (int i = 1; i <= n; ++i)
        v[i + n] += a[i];

    for (int i = 1; i <= (n << 1); ++i)
    {
        if (deq.front() <= i - n) deq.pop_front();
        for (; !deq.empty() && v[deq.back()] > v[i]; deq.pop_back());
        deq.push_back(i);
        if (sol < v[i] - v[deq.front()])
        {
            sol = v[i] - v[deq.front()];
            start = deq.front() - 1;
            finish = i - deq.front() + 1;
        }
    }

    g << sol << ' ' << start << ' ' << finish << '\n';
    g.close ();
    return 0;
}