Cod sursa(job #1723834)

Utilizator antanaAntonia Boca antana Data 1 iulie 2016 16:46:04
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include<deque>
#define MAXN 200000
using namespace std;
int v[2*MAXN+1];
long long s[2*MAXN+1];
deque<int>dq;
int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    int n, posmax, lmax, t;
    long long maxs;
    scanf("%d", &n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d", &v[i], &t);
        if(!t) v[i]*=-1;
        v[i+n]=v[i];
    }
    for(int i=1;i<=n*2;++i)
        s[i]=s[i-1]+v[i];
    maxs=s[1];
    posmax=lmax=1;
    dq.push_back(1);
    for(int i=2;i<2*n;++i)
    {
        if(dq.front() < i-n)
            dq.pop_front();
        if(s[i]-s[dq.front()] > maxs)
        {
            maxs=s[i]-s[dq.front()];
            posmax=dq.front() + 1;
            lmax=i-dq.front();
        }
        while(!dq.empty() && s[i] < s[dq.back()])
            dq.pop_back();
        dq.push_back(i);
    }
    printf("%lld %d %d",maxs, posmax, lmax);
    return 0;
}