Cod sursa(job #1984897)

Utilizator giotoPopescu Ioan gioto Data 26 mai 2017 14:51:12
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
using namespace std;

long long n, a[400002], dq[400002], Sum[400002], ind[400002];
int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    scanf("%d", &n);
    bool ok = 0;
    for(int i = 1; i <= n ; ++i){
        scanf("%d%d", &a[i], &ok);
        if(ok == 0) a[i] = -a[i];
        a[n + i] = a[i];
    }
    long long Front = 1, Back = 0, Max = -4000000000, L = 0, pos = 0;
    dq[++Back] = 0;
    for(int i = 1; i <= n * 2; ++i){
        Sum[i] = Sum[i - 1] + a[i];
        while(Back >= Front && Sum[i] <= Sum[dq[Front]])
            --Back;
        dq[++Back] = i;
        if(dq[Front] <= i - n) ++Front;
        ind[i] = dq[Front];
    }
    for(int i = 1;  i <= n * 2; ++i){
        if(Sum[i] - Sum[ind[i - 1]] > Max)
        {Max = Sum[i] - Sum[ind[i - 1]], pos = ind[i - 1] + 1; L = i - ind[i - 1];}

    }
    printf("%lld %lld %lld", Max, pos, L);
    return 0;
}