Cod sursa(job #3264327)

Utilizator Victor5539Tanase Victor Victor5539 Data 20 decembrie 2024 13:55:46
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <climits>
#define int long long

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


const int MAX=2e5;
int n,i,v[2*MAX+5],sol=INT_MIN,poz=INT_MAX,lmin=INT_MAX,val,sp[2*MAX+5],lungime,ind;
deque <int> dq;
signed main()
{
    fin>>n;
    for (i=1; i<=n; i++)
    {
        fin>>v[i]>>val;
        if (val==0)
            v[i]=-v[i];
    }

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

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


    for (i=1; i<=2*n; i++)
    {
        if (dq.front()==i-n-1)
            dq.pop_front();

        while (!dq.empty() && sp[dq.back()]>sp[i-1])
            dq.pop_back();

        dq.push_back(i-1);

        ind=dq.front()+1;
        lungime=i-ind+1;
        val=sp[i]-sp[ind-1];

        if (val>sol)
        {
            sol=val;
            poz=ind;
            lmin=lungime;
        }
        else
        {
            if (val==sol)
            {
                if (ind<poz)
                {
                    poz=ind;
                    lmin=lungime;
                }
                else if (ind==poz)
                {
                    if (lungime<lmin)
                        lmin=lungime;
                }
            }
        }
    }


    fout<<sol<<" "<<poz<<" "<<lmin;



    return 0;
}