Cod sursa(job #2118312)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 30 ianuarie 2018 14:44:06
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>
#define DIM 200005
using namespace std;

ifstream in("buline.in");
ofstream out("buline.out");

int n, culoare, sum;
int maxi, max_poz, max_l;
int mini, min_poz, min_l;
int v[DIM], subsec[DIM], l[DIM];

int main()
{

    in>>n;
    for( int i = 1; i <= n; i++ )
    {
        in>>v[i]>>culoare;
        if( culoare == 0 )
            v[i] = -v[i];

        sum += v[i];
    }

    ///SUBSEC DE SUMA MAXIMA
    subsec[1] = v[1];
    l[1] = 1;

    for( int i = 2; i <= n; i++ )
        if( subsec[i - 1] + v[i] >= v[i] )
        {
            subsec[i] = subsec[i - 1] + v[i];
            l[i] = l[i - 1] + 1;
        }
        else
        {
            subsec[i] = v[i];
            l[i] = 1;
        }

    maxi = subsec[1];
    max_poz = 1;
    max_l = 1;
    for( int i = 2; i <= n; i++ )
        if( maxi < subsec[i] )
        {
            maxi = subsec[i];
            max_poz = i - l[i] + 1;
            max_l = l[i];
        }

    ///SUBSEC DE SUMA MINIMA

    subsec[1] = v[1];
    l[1] = 1;

    for( int i = 2; i <= n; i++ )
        if( subsec[i - 1] + v[i] <= v[i] )
        {
            subsec[i] = subsec[i - 1] + v[i];
            l[i] = l[i - 1] + 1;
        }
        else
        {
            subsec[i] = v[i];
            l[i] = 1;
        }

    mini = subsec[1];
    min_poz = 1;
    min_l = 1;
    for( int i = 2; i <= n; i++ )
        if( mini > subsec[i] )
        {
            mini = subsec[i];
            min_poz = i - l[i] + 1;
            min_l = l[i];
        }

    if( maxi > sum - mini )
        out<<maxi<<" "<<max_poz<<" "<<max_l;
    else
        out<<sum - mini<<" "<<min_poz + min_l<<" "<<n - min_l;

    return 0;
}