Cod sursa(job #1496962)

Utilizator mariakKapros Maria mariak Data 5 octombrie 2015 21:06:47
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <algorithm>
#define Dim 400002

using namespace std;
int n, Smax, L, F, x, c, s[Dim], p;
int d[Dim], st, dr;
void read()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &x, &c);
        if(c == 0)
            s[i] = s[i - 1] - x;
        else
            s[i] = s[i - 1] + x;
    }
    for(int i = n + 1; i <= 2 * n; ++ i)
        s[i] = s[i - 1] + s[i - n] - s[i - n - 1];
}
void solve()
{
    st = 1;
    dr = 0;
    for(int i = 1; i <= 2 * n; ++ i)
    {
        /// actualizez coada
        while(st <= dr && s[d[dr]] >= s[i])
            dr --;
        d[++ dr] = i;
        while(i - d[st] == n + 1)
            st ++;
        if(Smax == s[i] - s[d[st]] && F == d[st] + 1 && L > i - d[st])
            L = i - d[st];
        if(Smax < s[i] - s[d[st]])
        {
            Smax = s[i] - s[d[st]];
            F = d[st] + 1;
            L = i - d[st];
        }
    }
}
void write()
{
    printf("%d %d %d\n", Smax, F, L);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}