Cod sursa(job #445951)

Utilizator chrissBota Cristian chriss Data 24 aprilie 2010 16:09:15
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream.h>

const char iname[] = "buline.in";
const char oname[] = "buline.out";

const int MAXN = 200100;

int main()
{
    ifstream fin(iname);
    int n, S[MAXN],minSum = int(2e9),maxSum = -int(2e9),bestSum,s=0,sum=0,beg1,end1,beg2,end2,x,i,k,L;
    fin >> n;
    for (i=1; i<=n; ++i)
    {
        fin >> S[i];
        fin >> k;
        if(k==0)
            S[i]=-S[i];
        s+=S[i];
        if (sum > 0)
            sum = S[i], x = i;
        else
            sum += S[i];
        if (minSum > sum)
            minSum = sum, beg1 = x, end1 = i;
    }
    bestSum = s - minSum;
    L = n - (end1 - beg1 + 1);
    sum=0;
    for (i=1; i<=n; ++i)
    {
        if (sum < 0)
            sum = S[i], x = i;
        else
            sum += S[i];
        if (maxSum < sum)
            maxSum = sum, beg2 = x, end2 = i;
    }
    ofstream fout(oname);
    if(maxSum > bestSum)
        fout << maxSum << " " << beg2 << " " << (end2-beg2+1);
    else
        fout << bestSum << " " << end1 + 1 << " " << L;

    fin.close(), fout.close();
    return 0;
}