Cod sursa(job #1412184)

Utilizator alexndru.enacheiumei fhd alexndru.enache Data 1 aprilie 2015 10:16:13
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>

using namespace std;
int v[400005];
int main()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    int n, i, x, y, stm1, drm1, s, smax1, smin, smax2, stm2, drm2, stot, st, dr;
    scanf("%d", &n);
    stot = 0;
    for (i = 1; i <= n; i ++){
        scanf("%d%d", &x, &y);
        if (y == 0)
            v[i] = -x;
        else
            v[i] = x;
        stot += v[i];
    }
    s = smax1 = v[1];
    st = stm1 = drm1 = 1;
    for (i = 2; i <= n; i ++){
        if (s + v[i] > v[i])
            s += v[i];
        else
            s = v[i], st = i;
        if (s > smax1){
            stm1 = st;
            drm1 = i;
            smax1 = s;
        }
    }
    s = smin = v[1];
    st = stm2 = drm2 = 1;
    for (i = 2; i <= n; i ++){
        if (s + v[i] < v[i])
            s += v[i];
        else
            s = v[i], st = i;
        if (s < smin){
            stm2 = st;
            drm2 = i;
            smin = s;
        }
    }
    smax2 = stot - smin;
    st = (drm2 + 1) % n;
    dr = stm2 - 1;
    if (smax1 > smax2)
        printf("%d %d %d", smax1, stm1, drm1 - stm1 + 1);
    else
        printf("%d %d %d", smax2, st, n - (drm2 - stm2+ 1));
    return 0;
}