Cod sursa(job #1450582)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 13 iunie 2015 18:50:10
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <vector>
#include <deque>

using namespace std;

int n , i , bulina , ans , start , finish;

vector < int > a , dp;
deque < int > D;

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

    scanf("%d", &n);

    a = vector < int > (n + 1);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d %d", &a[i], &bulina);
        if (!bulina) a[i] = a[i] * (-1);
    }

    for (i = 1; i < n; ++i)
        a.push_back(a[i]);

    dp = vector < int > (n << 1);
    for (i = 1; i < (n << 1); ++i)
        dp[i] = dp[i-1] + a[i];


    ans = a[1]; start = 1; finish = 1;
    for (D.push_back(1), i = 2; i < (n << 1); ++i)
    {
        if (!D.empty() && D.front() + n == i)
            D.pop_front();

        while (!D.empty() && dp[D.back()] > dp[i])
            D.pop_back();

        if (dp[i] - dp[D.front()] > ans)
        {
            ans = dp[i] - dp[D.front()];
            start = D.front() + 1;
            finish = i;
        }

        D.push_back(i);
    }

    printf("%d %d %d\n", ans , start , finish - start + 1);

    return 0;
}