Cod sursa(job #848724)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 5 ianuarie 2013 18:34:19
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <cstring>
 
using namespace std;
 
ifstream in ("buline.in");
ofstream out ("buline.out");
 
int V[400010];
bool Viz[400010];
 
int main ()
{
    int N, i, Sum = 0, SumMin = 0, Best, BestMin, idx = 1, idxMin = 1, L, St, Dr, StMin, DrMin, S = 0;
    bool bila;
     
    in >> N;
     
    for (i = 1; i <= N; i ++){
        in >> V[i] >> bila;
         
        if (!bila)
            V[i] = ~V[i] + 1;
		
		S += V[i];
	}
    St = 1;
    Dr = 1;
	StMin = 1;
	DrMin = 1;
	Sum = SumMin = Best = BestMin = -(1 << 31);
	
    //for (i = 1; i <= (N << 1); i ++)
        //cout << V[i] << " ";
     
    for (i = 1; i <= N; i ++){
		if (Sum < 0)
			Sum = 0, idx = i;
		if (SumMin < 0)
			SumMin = 0, idxMin = i;
		
		Sum += V[i];
		SumMin += (~V[i] + 1);
        
        if (Sum > Best)
            Best = Sum, St = idx, Dr = i;
		if (SumMin > BestMin)
			BestMin = SumMin, StMin = idxMin, DrMin = i;
    }
	
	SumMin = S + BestMin;
	if (SumMin > Best)
		Best = SumMin, St = DrMin + 1, Dr = StMin + N - 1;
	
    out << Best << " " << St << " " << Dr - St + 1;
     
    return 0;
}