Cod sursa(job #1164143)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 1 aprilie 2014 21:22:31
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
using namespace std;
ifstream in("buline.in");
ofstream out("buline.out");

const int nmax = 200006;
long v[nmax], n, sact, beg, bestbeg, bestend, smax = -10000000000, lung, lmax, sum[nmax], poz[nmax];

int main(){
	int player_unu=0;

	in>>n;
	for(int i = 1 ; i<=n; i++)
	{
		int aux;
		in>>v[i]>>aux;

		if(aux==0)
			v[i] = -v[i];
	}

	smax = sact = v[n];
	bestbeg = beg = n; 
	lmax = 1;
    for (int i = n-1; i > 0; i--)
    {
        sact += v[i];
        if (sact <= v[i])
		{
			sact = v[i];
			beg = i;
		}
        if (smax<=sact)
		{
			smax = sact;
			bestbeg = i;
			lmax = beg - i + 1;
		}
    }

    for (int i = 1; i<=n; i++)
        sum[i] = sum[i-1] + v[i];

	poz[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        poz[i] = poz[i-1];
        if(sum[poz[i]]<sum[i])
			poz[i] = i;
    }

	sact = 0;
    for (int i = n; i>0; i--)
    {
        sact += v[i]; 
		beg = sact + sum[ poz[i-1] ];

        if(smax<beg || (smax == beg && bestbeg > i))
		{
            smax = beg;
			bestbeg = i;
			lmax = n-i+1+poz[i-1];
		}
    }

	out<<smax<<" "<<bestbeg<<" "<<lmax<<'\n';
	return player_unu;
}