Cod sursa(job #2588732)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 25 martie 2020 13:14:55
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const int N(5e5 + 5);
int n, v[N], x, sp[N], curr, res(-1e9), start, lenght;
deque<int> dq;
int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i] >> x;
        if (x == 0)
            v[i] = -v[i];
        sp[i] = sp[i-1] + v[i];
    }
    for (int i = n + 1; i <= 2 * n; ++i)
    {
        v[i] = v[i - n];
        sp[i] = sp[i-1] + v[i];
    }
    dq.emplace_back(0);
    for (int i = 1; i <= 2 * n; ++i)
    {
        while (!dq.empty() && i - dq.front() > n)
            dq.pop_front();
        while (!dq.empty() && sp[i] <= sp[dq.back()])
            dq.pop_back();
        if (!dq.empty())
        {
            curr = sp[i] - sp[dq.front()];
            if (res < curr)
                res = curr, start = dq.front() + 1, lenght = i - dq.front();
        }
        dq.emplace_back(i);
    }
    start %= n;
    if (start == 0)
        start = n;
    fout << res << ' ' << start << ' ' << lenght;
    PLEC
}