Cod sursa(job #3275267)

Utilizator KLNNNDanaila Calin KLNNN Data 9 februarie 2025 16:49:16
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, v[200005], smax = INT_MIN, smin = INT_MAX, s, sum, st_max, dr_max, st, st_min, dr_min;
bool t;

int main(void)
{
    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 > smax) { // actualizez suma maxima
            smax = s;
            st_max = st;
            dr_max = i;
        }
    }
    
    // PENTRU SUMA MINIMA PENTRU CAZUL CIRCULAR
    // analog ca la suma maxima
    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 < smin) { // actualizez suma minima
            smin = s;
            st_min = st;
            dr_min = i;
        }
    }
    
    // comparam suma maxima obtinuta cu cea care trece circular
    if (smax > sum - smin)
        g << smax << " " << st_max << dr_max - st_max + 1;
    else
        // *Calculăm corect poziția secvenței în cazul circular*
        // dr_min + 1 este prima poziție după secvența minimă
        // st_min - 1 este ultima poziție înainte de secvența minimă
        // n - dr_min reprezintă lungimea bucății rămase după eliminarea secvenței minime
        g << sum - smin << " " << dr_min + 1 << st_min - 1 + n - dr_min; 
    
    return 0;
}