Cod sursa(job #1984883)

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

int n, a[200002], dq[200002], Sum[200002];
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];
    }
    int Front = 1, Back = 0, Max = -200000000, L = 0, pos = 0;
    for(int i = 1; i <= n * 2; ++i){
        Sum[i] = Sum[i - 1] + a[i];
        if(Sum[i] < 0){
            while(Back >= Front && Sum[i] <= Sum[dq[Front]])
                --Back;
        }
        if(Sum[i] - Sum[dq[Front]] > Max) {
            Max = Sum[i] - Sum[dq[Front]];
            L = i - dq[Front];
            pos = dq[Front] + 1;
        }
        if(dq[Front] == i - n && Back > Front) ++Front;
        dq[++Back] = i;
    }
    printf("%d %d %d", Max, pos, L);
    return 0;
}