Cod sursa(job #1913398)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 8 martie 2017 12:46:29
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<bits/stdc++.h>
#define maxN 400005
using namespace std;
int n,st,dr,v[maxN],c;
long long s[maxN],sol=-LLONG_MAX;
int m[maxN];
deque<int> q;
int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&c);
        if(!c) v[i]=-v[i];
        v[n+i]=v[i];
    }
    for(int i=1;i<=(2*n);i++) s[i]=s[i-1]+1LL*v[i];
    //m[i]-indicele minimului dintre [s[1],s[i]]
    m[0]=0;
    for(int i=1;i<=n;i++)
    {
        if(s[m[i-1]]<=s[i])
        {
            m[i]=m[i-1];
        }
            else m[i]=i;
    }
    for(int i=1;i<=(2*n);i++)
    {
        while(!q.empty() && s[q.back()]>=s[i])
        {
            q.pop_back();
        }
        q.push_back(i);
        while(q.front()<=(i-n)) q.pop_front();
        if(i>n)
        {
            m[i]=q.front();
        }
    }
    for(int i=1;i<=2*n;i++)
    {
        if((s[i]-s[m[i-1]])>sol)
        {
            sol=s[i]-s[m[i-1]];
            st=m[i-1]+1;
            dr=i;
        }
    }
    printf("%lld %d %d\n",sol,st,dr-st+1);
    return 0;
}