Cod sursa(job #877617)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 12 februarie 2013 23:53:43
Problema Buline Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int dmin[200002], dmax[20002], v[20002];
int n,i,maxim,minim,u1,p1,p2,u2,pmax,pmin,umax,umin,lg,s,a,b;
int main () {
	
	fin>>n;
	for (i=1;i<=n;i++) {
		fin>>a>>b;
		if (b==0) 
			v[i]=(a*-1);
		else
			v[i]=a;
	}
	dmax[1]=v[1];
	dmin[1]=v[1];
	maxim=dmax[1];
	minim=dmin[1];
	p1=1;u1=1;
	p2=1;u2=1;
	pmax=1;umax=1;
	pmin=1;umin=1;
	for (i=2;i<=n;i++) {
       if (v[i] + dmax[i-1] >= v[i]) {
            dmax[i] = v[i]+dmax[i-1];
        } else {
            dmax[i] = v[i];
            p1 = i;
        }
		if (v[i]+dmin[i-1]< v[i])
			dmin[i]=v[i]+dmin[i-1];
		else {
			dmin[i]=v[i];
			p2=i;
		}
        if (dmax[i] > maxim) {
            maxim = dmax[i];
            pmax = p1;
            umax = i;
        } else
            if (dmax[i] == maxim)
                if (p1 == pmax && i<umax)
                    umax = i;
		if (dmin[i]<minim){
			minim=dmin[i];
			pmin=p2;
			umin=i;
		}else 
			if (dmin[i]== minim) 
				if (i==umin && p2<pmin) 
					pmin= p2;
    }
	lg=umax-pmax+1;
	for (i=umin+1;i<=n;i++) 
		s+=v[i];
	for (i=1;i<pmin;i++)
		s+=v[i];
	if (s>maxim) {
		maxim=s;
		pmax=umin+1;
		lg=n-(umin-pmin+1);
	}else
		if (s==maxim) {
			if (umin<pmax) {
				pmax=umin+1;
				lg=n-(umin-pmin+1);
			}
			if (umin==pmax && n - (umin-pmin+1) < umax-pmax+1) {
				pmax=umin+1;
				lg=n-(umin-pmin+1);
			}
		}
	
	fout << maxim<<" "<<pmax<<" "<<lg;
	
	return 0;
}