Cod sursa(job #1110987)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 18 februarie 2014 15:51:35
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <deque>

#define NMAX 400007

using namespace std;

deque< int > deq;
int v[NMAX], s[NMAX];
int n, poz, Lung, Max;

int main(){
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        int a;
        scanf("%d %d", &v[i], &a);
        if(a == 0)
            v[i] = -v[i];
        v[n + i] = v[i];
    }
    n = n * 2;
    for(int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + v[i];
    for(int i = 1; i <= n; ++i){
        while(!deq.empty() && s[i] <= s[deq.back()])
            deq.pop_back();
        deq.push_back(i);
        if(deq.front() == i - n / 2)
            deq.pop_front();
        if(Max < s[i] - s[deq.front()]){
            Max = s[i] - s[deq.front()];
            poz = deq.front() + 1;
            Lung = i - poz + 1;
        }
    }
    printf("%d %d %d", Max, poz, Lung);
    return 0;
}