Cod sursa(job #3320003)

Utilizator boboc132Boboc Teodor boboc132 Data 4 noiembrie 2025 08:28:01
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <iostream>
#include <fstream>
using namespace std;

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

struct bila{
    int nr,cul;
};

long long S_max,P_max,L_max,S_min,sumtotal,S_circ;
int n;
int P_min,D_min;
bila bil[200005];

int mini(int a,int b){
    return (a<b ? a : b);
}

void citire(){
    in>>n;
    sumtotal = 0;
    for(int i=1;i<=n;i++){
        in>>bil[i].nr>>bil[i].cul;
        if(bil[i].cul==0) bil[i].nr = -bil[i].nr;
        sumtotal += bil[i].nr;
    }
}

void kadane1(){
    long long cur_sum = bil[1].nr;
    int ind = 1;
    S_max = cur_sum;
    P_max = 1;
    L_max = 1;
    for(int i=2;i<=n;i++){
        if(cur_sum < 0){
            cur_sum = bil[i].nr;
            ind = i;
        } else {
            cur_sum += bil[i].nr;
        }
        int cur_len = i - ind + 1;
        if(cur_sum > S_max){
            S_max = cur_sum;
            P_max = ind;
            L_max = cur_len;
        } else if(cur_sum == S_max){
            if(ind < P_max){
                P_max = ind;
                L_max = cur_len;
            } else if(ind == P_max){
                L_max = mini((int)L_max, cur_len);
            }
        }
    }
}

void kadane2(){
    long long cur_sum = bil[1].nr;
    int ind = 1;
    S_min = cur_sum;
    P_min = 1;
    D_min = 1;
    for(int i=2;i<=n;i++){
        if(cur_sum > 0){
            cur_sum = bil[i].nr;
            ind = i;
        } else {
            cur_sum += bil[i].nr;
        }
        if(cur_sum < S_min){
            S_min = cur_sum;
            P_min = ind;
            D_min = i;
        }
    }
}

void afisarefinala(){
    S_circ = sumtotal - S_min;
    bool min_is_entire = (P_min == 1 && D_min == n);
    if(min_is_entire){
        out<<S_max<<" "<<P_max<<" "<<L_max<<"\n";
        return;
    }
    int P_circ = (D_min % n) + 1;
    int len_min = D_min - P_min + 1;
    int L_circ = n - len_min;
    if(S_circ > S_max){
        out<<S_circ<<" "<<P_circ<<" "<<L_circ<<"\n";
    } else if(S_circ < S_max){
        out<<S_max<<" "<<P_max<<" "<<L_max<<"\n";
    } else {
        if(P_circ < P_max){
            out<<S_circ<<" "<<P_circ<<" "<<L_circ<<"\n";
        } else if(P_circ > P_max){
            out<<S_max<<" "<<P_max<<" "<<L_max<<"\n";
        } else {
            if(L_circ < L_max) cout<<S_circ<<" "<<P_circ<<" "<<L_circ<<"\n";
            else out<<S_max<<" "<<P_max<<" "<<L_max<<"\n";
        }
    }
}

int main(){
    citire();
    kadane1();
    kadane2();
    afisarefinala();
    return 0;
}