Cod sursa(job #1254333)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 2 noiembrie 2014 15:53:56
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>
#include<iostream>
using namespace std;
ifstream in("buline.in");
ofstream out("buline.out");

int v[500009],n;

void citire()
{

    in>>n;
    int x,y;
    for(int i = 1 ; i <= n ; i++){
        in>>x>>y;
        if(y == 0){
            v[i] = -x;
        }
        else
            v[i] = x;
    }
    int c = n;
    for(int i = 1 ; i <= n ; i++)
        v[++c] = v[i];
    in.close();
}

int main()
{
    citire();
    int best = - 99999999,s = 1,lg = 0,sum = 0,bg = 1;
    for(int i = 1 ; i <= 2*n ; i++){

        if(sum < 0){
            s = i;
            sum = v[i];
        }
        else
            sum += v[i];
         if(sum > best && i-s+1 <= n){
                best = sum;
                bg = s;
                lg = i-s+1;
            }
    }
    out<<best<<" ";
    if(bg > n)
        out<<bg-n<<" ";
    else
        out<<bg<<" ";
    out<<lg;
    return 0;
}