Cod sursa(job #1496450)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 4 octombrie 2015 23:17:27
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int n;

int main ()
{
    ifstream fin("buline.in"); 
    ofstream fout("buline.out"); 
	int x, y;
	fin>>n;
	vector<int> v(n);

	for(int i=0;i<n;i++)
	{
		fin>>x>>y;
		v[i] = y?x:-x;
	}

	int start = 0;
	int length = 0;
    int sum = 0;
    int max = 0;
    int max_start = 0;
    int max_length = 0;

	for(int i=0;i<n;i++)
	{
        if(sum>=0)
        {
            sum+=v[i];
            length+=1;
        }
        else
        {
            sum = v[i];
            length = 1;
            start = i;
        }
        if(max<sum)
        {
            max = sum;
            max_start = start;
            max_length = length;
//            cout<<max_start<<" "<<max_length<<" "<<sum<<endl;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(i==start)
        {
            start++;
            length--;
            sum-=v[i];
            for(;v[start]<0 and start<n;start++)
            {
                sum-=v[start]; 
                length--;
            }
        }
        if(sum>=0)
        {
            sum+=v[i];
            length+=1;
        }    
        else
            break;
        if(max<sum)
        {
            max=sum;
            max_start = start; 
            max_length = length;
//            cout<<max_start<<" "<<max_length<<" "<<sum<<endl;
        }
    }    
    fout<<max<<" "<<max_start+1<<" "<<max_length;

    return 0;
}