Mai intai trebuie sa te autentifici.

Cod sursa(job #833336)

Utilizator adysnookAdrian Munteanu adysnook Data 12 decembrie 2012 14:30:59
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
using namespace std;
int const N=200000;
short b[N];
int n;
int S, P, L;
int dp1[N];
int dp2[N];
//dp1[i]=suma maxima pana la i
//dp2[i]=suma minima pana la i
int sgn(int a){
	return a<0;
}
int ST;
int Sm, SM;
int Pm, PM;
int Lm, LM;
int Lmc, LMc;
int main(){
    ifstream f("buline.in");
    f>>n;
    int i;
    int x;
    for(i=0; i<n; i++){
        f>>b[i];
        f>>x;
        b[i]=x?b[i]:-b[i];
		dp1[i]=b[i];
		dp2[i]=b[i];
		ST+=b[i];
    }
    f.close();

	SM=Sm=b[0];
	PM=Pm=0;
	LM=Lm=LMc=Lmc=1;

	for(i=1; i<n; i++){
		if(dp1[i-1]>0){
			dp1[i]+=dp1[i-1];
			LMc++;
		}else{
			LMc=1;
		}
		if(dp1[i]>SM){
			SM=dp1[i];
			PM=i-LMc+1;
			LM=LMc;
		}
		if(dp2[i-1]<0){
			dp2[i]+=dp2[i-1];
			Lmc++;
		}else{
			Lmc=1;
		}
		if(dp2[i]<Sm){
			Sm=dp2[i];
			Pm=i-Lmc+1;
			Lm=Lmc;
		}
	}

	if(SM>ST-Sm){
		S=SM;
		P=PM;
		L=LM;
	}else{
		S=ST-Sm;
		P=Pm+Lm;
		L=n-Lm;
	}
    
    ofstream g("buline.out");
    g<<S<<" "<<P+1<<" "<<L;
    g.close();
    return 0;
}