Cod sursa(job #3283917)

Utilizator Sincan_AlexandruSincan Alexandru Sincan_Alexandru Data 10 martie 2025 18:08:16
Problema Buline Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
using namespace std;

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

int n;
int v[200001];
bool albnegru;

int s[200001];
int st[200001],l[200001];
int stmax,lmax;
int maxi;

int smin[200001];
int mini;
int drmini;
int lmini;
int lmin[200001];

int suma;

int main()
{
    fin >> n;
    for(int i=1; i<=n; i++){
        fin >> v[i] >> albnegru;
        if(albnegru == 0) v[i] = -v[i]; 
        suma += v[i];
    }
    
    s[1] = v[1];
    st[1] = 1;
    for(int i=2; i<=n; i++){
        if(s[i-1] + v[i] >= v[i]){
            s[i] = s[i-1] + v[i];
            st[i] = st[i-1];
            l[i] = l[i-1] + 1;
        }
        else{
            s[i] = v[i];
            st[i] = i;
            l[i] = 1;
        }
    }

    maxi = -2e9-7;
    for(int i=1; i<=n; i++){
        if(s[i] > maxi){
            maxi = s[i];
            stmax = st[i];
            lmax = l[i];
        }
    }

    smin[1] = v[1];
    lmin[1] = 1;
    for(int i=2; i<=n; i++){
        if(smin[i-1] + v[i] <= v[i]){
            smin[i] = smin[i-1] + v[i];
            lmin[i] = lmin[i-1]++;
        }
        else{
            smin[i] = v[i];
            lmin[i] = 1;
        }
        drmini = i;
    }
    mini = 2e9+7;
    for(int i=1; i<=n; i++){
        if(smin[i] < mini){
            mini = smin[i];
            lmini = lmin[i];
            drmini = i + 1;
        }
    }

    if(suma - mini > maxi){
        maxi = suma - mini;
        fout << maxi << " " << drmini << " " << n - lmini + 1;
    }
    else{
        fout << maxi << " " << stmax << " " << lmax;
    }

    
    return 0;
}