Cod sursa(job #86875)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 25 septembrie 2007 20:51:13
Problema Buline Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#define INF 666000666

int N, V[400200], S[400200], DQ[400200], P[400200];

int main()
{
        int i, n, lo, hi, smax, p, l, s, pp;
        freopen("buline.in", "r", stdin);
        scanf("%d",&N);
        for (i = 1; i <= N; i++){scanf("%d%d", V+i, &p);
                                if(!p) V[i] = -V[i]; }
        for (i = 1; i <= N; i++) V[i+N] = V[i];
        for (i = 1, n = 2*N; i < n; i++) S[i] = S[i-1]+V[i];
        for (i = 1; i <= N; i++) {
            if (smax<V[i]) smax = V[i], p = i, l = 1;
            if (smax<S[i]) smax = S[i], p = 1, l = i; }
        for (DQ[0] = INF, i = hi = 1, p = l = lo = 0; i <= n; i++)
        {
                while (i-P[lo]>=N && lo<hi) lo++;
                if (lo==hi) break;
                while (DQ[hi-1]>S[i] && hi>lo) hi--;
                DQ[hi] = S[i]; P[hi++] = i; s = S[i]-DQ[lo]; pp = P[lo]+1;
                if (smax<s) smax = s, p = pp, l = i-pp+1;
                else{if (smax==(S[i]-DQ[lo]))
                        if ((p>pp)||((p==pp)&&(l>(i-pp+1)))) p = pp, l = i-pp+1;}
        }
        freopen("buline.out", "w", stdout);
        printf("%d %d %d\n", smax, p, l);
        return 0;
}