Cod sursa(job #3265945)

Utilizator maxtraAlex Deonise maxtra Data 4 ianuarie 2025 13:23:52
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, v[200005], smax = INT_MIN, smin = INT_MAX, s, sum, stMax, drMax, st, stMin, drMin;
bool t;
int main() 
{
    fin >> n;
    
    for (int i = 1; i <= n; i++) {
        fin >> v[i] >> t;
        
        if (!t) {
            v[i] *= (-1); // valori negative pentru buline negre
        }
        
        sum += v[i]; // calculez suma totala
    }
    
    s = v[1]; // initializez suma curenta
    stMax = drMax = 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;
            stMax = st;
            drMax = i;
        }
    }
    
    // analog se face pentru suma minima
    s = v[1]; 
    stMin = st = 1; 
    
    for (int i = 2; i <= n; i++) {
        if (s + v[i] <= v[i]) { 
            s += v[i];
        } else { 
            s = v[i];
            st = i;
        }
        
        if (s < smin) { 
            smin = s;
            stMin = st;
            drMin = i;
        }
    }
    
    // comparam suma maxima obtinuta cu cea care trece prin cerc
    if (smax > sum - smin) {
        fout << smax << " " << stMax << " " << drMax - stMax + 1;
    } else {
        fout << sum - smin << " " << drMin + 1 << " " << stMin - 1 + n - drMin;

    }
    return 0;
}