Cod sursa(job #2013229)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 20 august 2017 20:21:21
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int i,n,maxi,l,poz,x,s[400001],v[400001];
deque<int>d;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>v[i]>>x;
        if(x==0)
            v[i]=-v[i];
    }
    for(i=1;i<=n;i++)
        v[i+n]=v[i];
    for(i=1;i<=2*n;i++)
        s[i]=s[i-1]+v[i];
    d.push_back(1);
    int sz=0;
    for(i=2;i<=2*n;i++)
    {
        if(i-d[0]>n)
            d.pop_front(),--sz;
        if(s[i]-s[d[0]]>maxi)
        {
            maxi=s[i]-s[d[0]];
            poz=d[0]+1;
            l=i-d[0];
        }
        while(sz>=0 && s[i]<s[sz])
            d.pop_back(),--sz;
        d.push_back(i),++sz;
    }
    g<<maxi<<' '<<poz<<' '<<l;
    return 0;
}