Cod sursa(job #1409267)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 30 martie 2015 14:23:20
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
using namespace std;
int v[400005];
int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    int n, nr, c, s, st, l, smax, stmax, lmax;
    scanf("%d",&n);
    for (register int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &nr, &c);
        if (c == 1)
            v[i] = v[i + n] = nr;
        else
            v[i] = v[i + n] = -nr;
    }
    s = v[1]; st = 1; l = 1;
    smax = v[1]; stmax = 1; lmax = 1;
    for (register int i = 2; i < 2 * n; ++i)
    {
        while (l > 1 && v[st] < 0)
        {
            s -= v[st];
            ++st;
            --l;
        }
        if (l == n)
            if (s + v[i] - v[i - l] > v[i])
            {
                ++st;
                s = s + v[i] - v[i - l];
            }
            else
            {
                s = v[i];
                st = i;
                l = 1;
            }
        else
            if (s + v[i] > v[i])
            {
                ++l;
                s += v[i];
            }
            else
            {
                s = v[i];
                st = i;
                l = 1;
            }

        if (s > smax)
        {
            smax = s;
            stmax = st;
            lmax = l;
        }
    }
    printf ("%d %d %d\n", smax, stmax, lmax);
    return 0;
}