Cod sursa(job #1522500)

Utilizator LucianTLucian Trepteanu LucianT Data 11 noiembrie 2015 19:27:30
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <algorithm>
#include <deque>
#include <climits>
#define maxN 400005
using namespace std;
int n, i, j, sol=-INT_MAX, v[maxN], cl, fin, p, s[maxN];
deque <int> q;
int semn[] = {-1, 1};
int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
    {
        scanf("%d %d", &v[i], &cl);
        v[i] *= semn[cl];
    }
    p = 0;
    for(i = 1; i < n; i++)
        v[n + i] = v[i];
    q.push_front(0);
    for(i = 1; i <= 2 * n-1; i++)
    {
        s[i] = s[i-1] + v[i];
        while(!q.empty() && s[q.back()]>s[i])
            q.pop_back();
        q.push_back(i);
        if(i - n == q.front()) q.pop_front();
        if(s[q.front()] > 0)
            if(s[i] > sol && i <= n)
            {
                sol = s[i], p = 1, fin = i;
            }
        if(s[i] - s[q.front()] > sol)
            sol = s[i]-s[q.front()], p = q.front()+1, fin = i-q.front();
    }
    printf("%d %d %d", sol, p, fin);
    return 0;
}