Cod sursa(job #1532408)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 21 noiembrie 2015 15:34:18
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <deque>
#include <algorithm>

using namespace std;

int v[400010];
deque <int> dq;

int main ()
{
    freopen ("buline.in", "r", stdin);
    freopen ("buline.out", "w", stdout);

    int n;
    scanf ("%d", &n);

    for (int i = 1;; ++i)
    {
        int x, y;
        scanf ("%d %d", &x, &y);

        y = !y ? -1 : 1;
        y *= x;

        v[i] = v[i - 1] + y;
        v[i + n] = y;

        if (i == n) break;

        while (!dq.empty () && v[i] >= v[dq.back ()])
            dq.pop_back ();

        dq.push_back (i);
    }

    for (int i = n + 1; i < 2 * n; ++i)
        v[i] += v[i - 1];

    int ma = -100000, poz, len;
    for (int i = n; i < 2 * n; ++i)
    {
        if (!dq.empty () && dq.front () <= i - n) dq.pop_front ();

        while (!dq.empty () && v[i] >= v[dq.back ()])
            dq.pop_back ();

        dq.push_back (i);

        if (v[dq.front ()] - v[i - n] > ma) ma = v[dq.front ()] - v[i - n], poz = i - n + 1, len = dq.front () - (i - n);
    }

    printf ("%d ", ma);
    printf ("%d ", poz);
    printf ("%d\n", len);

    return 0;
}