Cod sursa(job #3287280)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 17 martie 2025 14:19:20
Problema Buline Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>

using namespace std;

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

const int sizee = 200000;
int n, val, type, v[sizee + 2];
int totalsum;
int smax = -(1 << 30);

struct komp{ int maxi, st, dr; };

komp summax(){
    komp bestt = {-(1 << 30), 0, 0};
    int summy = 0, __leftt = 0;
    for(int i = 1; i <= n; i++){
        summy += v[i];
        if(summy < 0){
            summy = 0;
            __leftt = i + 1;
        }
        if(summy > bestt.maxi){
            bestt.maxi = summy;
            bestt.st = __leftt;
            bestt.dr = i;
        }
    }
    return bestt;
}

int main(){
    in>>n;
    for(int i = 1; i <= n; i++){
        in>>val>>type; val *= (type ? 1 : -1);
        v[i] = val; totalsum += v[i];
    }
    komp p = summax();
    for(int i = 1; i <= n; i++) v[i] *= (-1);
    komp m = summax();

    ///out<<p.maxi<<" "<<p.st<<" "<<p.dr<<"\n";
    ///out<<m.maxi<<" "<<m.st<<" "<<m.dr<<"\n";

    if(p.maxi > totalsum + m.maxi){
        out<<p.maxi<<" "<<p.st<<" "<<p.dr<<"\n";
    }else{
        out<<totalsum + m.maxi<<" "<<((m.dr == n) ? 1 : m.dr + 1)<<" "<<n - (m.dr - m.st + 1)<<"\n";
    }

    return 0;
}