Cod sursa(job #2336032)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 4 februarie 2019 18:46:15
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <climits>
#define maxn 200000

using namespace std;

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

long long n, v[2 * maxn + 2];
long long dq[2 * maxn + 2], fr, bk, s = LLONG_MIN, posi, posj;

int main()
{
    int semn;
    in >> n;
    for (int i = 1; i <= n; ++i)
    {
        in >> v[i] >> semn;
        if (semn)
            v[i + n] = v[i];
        else
            v[i + n] = v[i] = -v[i];
    }
    fr = 1;
    bk = 0;
    for (int i = 1; i <= 2 * n; ++i)
    {
        v[i] += v[i - 1];
        if (s < v[i] - v[dq[fr]])
        {
            s = v[i] - v[dq[fr]];
            posi = i;
            posj = dq[fr] + 1;
        }
        while (fr <= bk && v[i] <= v[dq[bk]])
            --bk;
        dq[++bk] = i;
        if (i - dq[fr] == n)
            ++fr;
    }
    out << s << " " << posj << " " << posi - posj + 1;
    return 0;
}