Cod sursa(job #3275222)

Utilizator PredaBogdanPreda Bogdan PredaBogdan Data 9 februarie 2025 14:47:00
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 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;
    
    cin >> n;
    
    for(int i = 1; i <= n; i++) {
        cin >> 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 > suma - sum_min)
        g << sum_max << " " << st_max << " " << dr_max - st_max + 1;
    else 
        g << suma - sum_min << " " << dr_min + 1 << " " << st_min - 1 + n - dr_min; 

    return 0;
}