Cod sursa(job #1106197)

Utilizator diana97Diana Ghinea diana97 Data 12 februarie 2014 17:13:43
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("buline.in");
ofstream g ("buline.out");

int n;
int st, dr, front, back;
int v[400005], s[400005], dq[400005];

void citeste () {
    int x, semn;
    f >> n;
    for (int i = 1 ; i <= n; i++) {
        f >> x >> semn;
        if (semn) v[i] = x;
        else v[i] = -x;
        v[i + n] = v[i];
    }
    x = 2 * n;
    for (int i = 1; i <= x; i++) {
        s[i] = s[i - 1] + v[i];
    }
}

void rezolva () {
    int maxim = s[n], l = 2 * n;
    st = 1;
    dr = n;
    front = 1; back = 0;
    for (int i = 1; i <= l; i++) {
        while (front <= back && s[i] < s[dq[back]]) back--;
        dq[++back] = i;
        if (dq[front] == i - n) front++;
        if (maxim < s[i] - s[dq[front]]) {
            maxim = s[i] - s[dq[front]];
            st = dq[front] + 1;
            dr = i;
        }
    }
    g << maxim << ' ' << st << ' ' << dr - st + 1 << '\n';
}

int main () {
    citeste ();
    rezolva ();
    return 0;
}