Cod sursa(job #2118402)

Utilizator AndaionicaIonica Anda Maria Andaionica Data 30 ianuarie 2018 17:02:29
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
/*int v[200001],n,i,k,s,l,p,smax,l1,p1,smin,l2,p2,l3,p3,s2,S;
int main()
{
    f>>n;
    smax=-10001;
    s=-1;
    for(i=1;i<=n;i++)
    {
        f>>v[i]>>k;
        v[i]+=2*(k-1)*v[i];
        S+=v[i];
        if(s>=0)
        {
            s+=v[i];
            l++;
        }
            else
            {
                p=i;
                s=v[i];
                l=1;
            }
        if(smax<s)
        {
            smax=s;
            p1=p;
            l1=l;
        }
        if(s2<0)
        {
            s2+=v[i];
            l2++;
        }
            else
            {
                p2=i;
                s2=v[i];
                l2=1;
            }
        if(smin>s2)
        {
            smin=s2;
            p3=p2;
            l3=l2;
        }
    }
    if(smax<S-smin)
    {
        smax=S-smin;
        p1=p3+l3;
        l1=n-l3;
    }
    g<<smax<<" "<<p1<<" "<<l1;
    return 0;
}*/
int n,dr,st,i,k,Max,p,l,v[400001],s[400001];
int main(){
    f>>n;
    dr=1;st=1;Max=-10001;
    for(i=1;i<=n;i++){
        f>>s[i]>>k;
        s[i]+=2*s[i]*(k-1)+s[i-1];
        while(dr>=1&&s[i]<=s[v[dr]])
            dr--;
        dr++;
        v[dr]=i;
        if(Max<s[i]-s[v[1]]){
            Max=s[i]-s[v[1]];
            p=v[st]+1;
            l=i-p+1;
        }
        s[i+n]=s[i];
    }
    for(i=n+1;i<=2*n;i++){
        s[i]+=s[n];
        while(st<=dr&&s[i]<=s[v[dr]])
            dr--;
        dr++;
        v[dr]=i;
        if(v[st]==i-n-1)
            st++;
        if(Max<s[i]-s[v[st]]){
            Max=s[i]-s[v[st]];
            p=(v[st]+1)%n;
            l=i-v[st];
        }
    }
    g<<Max<<" "<<p<<" "<<l;
}