Cod sursa(job #3275223)

Utilizator PredaBogdanPreda Bogdan PredaBogdan Data 9 februarie 2025 14:49:04
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int n, v[200005], sum_max = INT_MIN, sum_min = INT_MAX, s = 0, sum = 0, st_max = 0, dr_max = 0,
        st, st_min = 0, dr_min = 0;
    bool t;
    
    f >> n;
    
    for(int i = 1; i <= n; i++) {
        f >> v[i] >> t;
        if(!t)
            v[i] *= -1; // valori negative pentru bile negre
            
        sum += v[i]; // calculez suma totala
    }

    // PENTRU SUMA MAXIMA
    s = v[1]; // initializez suma curenta
    st_max = dr_max = st = 1; // pozitia secventei maxime

    for(int i = 2; i <= n; i++) {
        if (s + v[i] >= v[i]) // extind secventa curenta
            s += v[i];
        else { // incep o noua secventa
            s = v[i];
            st = i;
        }
        
        if (s > sum_max) { // actualizez suma maxima
            sum_max = s;
            st_max = st;
            dr_max = i;
        }
    }
    
    // ANALOG PENTRU SUMA MINIMA
    s = v[1]; // initializez suma curenta
    st_min= dr_min = st = 1; // pozitia secventei minime

    for (int i = 2; i <= n; i++) {
        if (s + v[i] <= v[i]) // extind secventa curenta
            s += v[i];
        else { // incep o noua secventa
            s = v[i];
            st = i;
        }
        
        if (s < sum_min) { // actualizez suma minima
            sum_min = s;
            st_min = st;
            dr_min = i;
        }
    }
    
    // comparam suma maxima obtinuta cu cea care trece prin cerc
    if (sum_max > sum - sum_min)
        g << sum_max << " " << st_max << " " << dr_max - st_max + 1;
    else 
        g << sum - sum_min << " " << dr_min + 1 << " " << st_min - 1 + n - dr_min; 

    return 0;
}