Cod sursa(job #1006507)

Utilizator poptibiPop Tiberiu poptibi Data 7 octombrie 2013 10:28:43
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <algorithm>
using namespace std;

const int NMAX = 400010;

int N, V[NMAX], C, P, St, L;
deque<int> D;
long long Sum[NMAX], Max;

int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i %i", &V[i], &C);
        if(C == 0) V[i] = -V[i];
        V[i + N] = V[i];
    }

    for(int i = 1; i <= 2 * N; ++ i)
        Sum[i] = Sum[i - 1] + 1LL * V[i];

    for(int i = 1; i <= 2 * N; ++ i)
    {
        while(!D.empty() && Sum[D.back()] > Sum[i]) D.pop_back();
        D.push_back(i);
        while(!D.empty() && D.front() <= i - N) D.pop_front();

        if(!D.empty() && D.front() < i - 1)
        {
            if(Sum[i] - Sum[D.front()] > Max) Max = Sum[i] - Sum[D.front()], P = D.front() + 1, St = i;
            else if(Sum[i] - Sum[D.front()] == Max && D.front() + 1 < P) P = D.front() + 1, St = i;
        }
    }

    while(Sum[St] == Sum[St - 1]) St --;

    printf("%lld %i %i\n", Max, P, St - P + 1);

    return 0;
}