Cod sursa(job #2111775)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 22 ianuarie 2018 17:50:42
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, c, maxi, pf, lf;
int arr[400004], s[400004], p[400004], l[400004];

/*
    S[I] = SUBSECVENTA DE SUMA MAXIMA CE SE TERMINA PE POZ I
    P[I] = POZITIA DE INCEPUT A SUBSECVENTEI DE SUMA MAXIMA CARE SE TERMINA PE POZ I
    L[I] = LUNGIMEA SUBSECVENTEI DE SUMA MAXIMA CARE SE TERMINA PE POZ I
*/

int main()
{

    in>>n;
    for( int i = 1; i <= n; i++ )
    {
        in>>arr[i]>>c;
        arr[i] = ( c == 0 )? -arr[i] : arr[i];
    }

    for( int i = 1; i <= n-1; i++ )
        arr[i + n] = arr[i];

    s[1] = arr[1];
    l[1] = 1;
    p[1] = 1;
    for( int i = 2; i <= 2*n - 1; i++ )
        if( s[i-1] + arr[i] > arr[i] )
        {
            s[i] = s[i-1] + arr[i];
            p[i] = p[i-1];
            l[i] = l[i-1] + 1;
        }
        else
        {
            s[i] = arr[i];
            p[i] = i;
            l[i] = 1;
        }

    maxi = -0x7fffffff;
    for( int i = 1; i <= 2*n - 1; i++ )
        if( maxi < s[i] )
        {
            maxi = s[i];
            pf = p[i];
            lf = l[i];
        }

    out<<maxi<<" "<<pf<<" "<<lf;

    return 0;
}