Cod sursa(job #2931328)

Utilizator alessiamtr12Mitrica Alessia alessiamtr12 Data 30 octombrie 2022 21:13:45
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb


#include <fstream>
#include<climits>
#include<deque>
#define NMAX 200001
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,v[2*NMAX],x,st,dr,p,lg;
bool tip;
long long s,smax=LONG_MIN;
int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>x>>tip;
        if(tip==0)
            x=-x;
        v[i]=x;
    }
    for(int i=n+1; i<=2*n; i++)
        v[i]=v[i-n];

    deque<int> q;
    q.push_front(1);
    st=1;
    lg=1;
    for(int i=2; i<=2*n; i++)
    {
        v[i]+=v[i-1];
        while(!q.empty() && i-q.front()>n)
            q.pop_front();

        if(v[i]-v[q.front()]>smax)
        {
            smax=v[i]-v[q.front()];
            st=q.front()+1;
            lg=i-q.front();
        }

        while(!q.empty() && v[q.back()]>v[i])
            q.pop_back();

        q.push_back(i);
    }
    fout<<smax<<" "<<st<<" "<<lg;
    return 0;
}