Cod sursa(job #2098117)

Utilizator osiaccrCristian Osiac osiaccr Data 2 ianuarie 2018 13:48:38
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#define DEF 200010
#define INF 1 << 29

using namespace std;

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

int n, v[2 * DEF], s[2 * DEF], h[2 * DEF], Min, Max = -INF, st, dr, p, l;

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        int temp;
        fin >> v[i] >> temp;
        if (!temp) {
            v[i] *= -1;
        }
    }
    for (int i = 1; i < n; ++ i) {
        v[i + n] = v[i];
    }

    s[1] = v[1];

    h[++ dr] = 1;

    Min = INF;

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

        Min = s[h[st]];

        int temp = s[i] - Min;
        if (temp > Max) {
            Max = temp;
            p = h[st] + 1;
            l = i - p + 1;
        }

        while (st <= dr && s[i] < s[h[dr]]) {
            -- dr;
        }

        h[++ dr] = i;

        if (h[st] < i - n + 1)
            ++ st;
    }

    fout << Max << " " << p << " " << l;

    return 0;
}