Cod sursa(job #3266652)

Utilizator XxThornadoxXStoica Teodora XxThornadoxX Data 9 ianuarie 2025 18:39:01
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <deque>
#include <fstream>

using namespace std;

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

int n, a[400001], s[400001];
deque<int> dq;

int main()
{
    fin >> n;
    int check;

    for(int i = 1; i <= n; i++)
    {
        fin >> a[i] >> check;

        if(!check)
            a[i] = -a[i];
        a[i+n] = a[i];
    }

    dq.push_back(1);
    int maxx = -1, st = 0, l;

    for(int i = 2; i <= 2*n; i++)
    {
        s[i] = s[i-1] + a[i];
        while(!dq.empty() && i - dq.front() > n)
            dq.pop_front();

        if(s[i] - s[dq.front()] > maxx)
        {
            maxx = s[i] - s[dq.front()];
            st = dq.front()+1;
            l = i-dq.front();
        }

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

        dq.push_back(i);
    }

    fout << maxx << " " << st << " " << l;
}