Cod sursa(job #1694528)

Utilizator sucureiSucureiRobert sucurei Data 25 aprilie 2016 16:04:48
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>
#include<deque>
#include<vector>
#include <cstring>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");



int n,m,k,i,j,p,x,y,a[400005],t,sol=-2000000000,poz1,poz2;
deque<int> d;



int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        if(y==0) x=-x;
        a[i]=a[i+n]=x;

    }

    for(i=1;i<=2*n;i++)
    {
        a[i]=a[i]+a[i-1];
    }

    for(i=1;i<=2*n;i++)
    {
        while(!d.empty() && a[d.back()]>=a[i]){
            d.pop_back();
        }
        d.push_back(i);
        if(d.front()==i-n)
            d.pop_front();
        if(sol < (a[i]-a[d.front()]) )
        {
            sol=a[i]-a[d.front()];
            poz1=d.front()+1;
            poz2=i-d.front();
        }
        //fout<<a[i]<<" "<<a[d.front()]<<"\n";

    }
    fout<<sol<<" "<<poz1<<" "<<poz2<<"\n";

    for(i=1;i<=2*n;i++)
    {
        //fout<<a[i]<<" ";
    }
}