Cod sursa(job #1984900)

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

long long n, a[400002], dq[400002], Sum[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[Back]])
            --Back;
        if(Sum[i] - Sum[dq[Front]] > Max && Back >= Front) {
            Max = Sum[i] - Sum[dq[Front]];
            L = i - dq[Front];
            pos = dq[Front] + 1;
        }
        dq[++Back] = i;
        if(dq[Front] <= i - n) ++Front;
    }
    printf("%lld %lld %lld", Max, pos, L);
    return 0;
}