Cod sursa(job #60910)

Utilizator DastasIonescu Vlad Dastas Data 17 mai 2007 17:48:11
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#define MAX 200001
#define max(a, b) (((a) > (b))?(a):(b))

FILE *in = fopen("buline.in","r"), *out = fopen("buline.out","w");
int n;
int a[MAX];
int s[MAX] = {0};
int t[MAX] = {0};

void read()
{
    fscanf(in, "%d", &n);

    int b = 0;
    for ( int i = 1; i <= n; ++i )
    {
        fscanf(in, "%d %d", &a[i], &b);

        if ( b == 0 )
            a[i] *= -1;

        s[i] = s[i-1] + a[i];
        t[i] = max(t[i-1], s[i]);
    }
}

int main()
{
    read();

    int best = t[1]+s[n]-s[1];
    int p = 1;
    int l = n-1;

    for ( int i = 1; i <= n; ++i )
    {
        if ( t[i-1]+s[n]-s[i-1] > best )
        {
            best = t[i-1]+s[n]-s[i-1];
            p = i;
            l = i;
        }

    }
    fprintf(out, "%d %d %d\n", best, p, l);

    return 0;
}