Cod sursa(job #852191)

Utilizator HypherionRobert Mandache Hypherion Data 10 ianuarie 2013 23:16:12
Problema Buline Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <vector>
#include <fstream>
using namespace std;

int main(){
	
	ifstream in ("buline.in");
	ofstream out("buline.out");
	int n,x;
	in>>n;
	vector<int> v(n+n+1);
	for(int i=0;i<n;i++){
            in>>v[i]>>x;
            if(x==0)
                v[i]=-v[i];
        }
	for(int i=n;i<v.size();i++)
            v[i]=v[i-n];	
        int maxSum=0;
        int maxEndingHere=0;
        int start=0;
        int end=0;
        int maxStart=0;
        for(int i=0;i<v.size();i++){
            if(maxEndingHere+v[i]<0){
                maxEndingHere=0;
                start=i+1;
            }
            else 
                maxEndingHere=maxEndingHere+v[i];
            if(maxSum<maxEndingHere){
                maxSum=maxEndingHere;
                maxStart=start;
                end=i;
            }
            if(i-start==n-1){
				i=start;
                start++;
                maxEndingHere=0;
            }
        }
		out<<maxSum<<" "<<maxStart+1<<" "<<end-maxStart+1;
	return 0;
}