Cod sursa(job #3248792)

Utilizator prares06Papacioc Rares-Ioan prares06 Data 13 octombrie 2024 11:43:47
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<bits/stdc++.h>
using namespace std;

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

const int MAX = 2e5 + 5;
int n, x, semn, stotal, pmax, pmin, v[MAX], smax[MAX], smin[MAX], pozmax[MAX], pozmin[MAX];

int main(){
    fin >> n;

    smin[1] = 1;

    for(int i = 1; i <= n; ++i){
        fin >> v[i] >> semn;
        if(!semn)
            v[i] = -v[i];
        stotal += v[i];
    }

    for(int i = 1; i <= n; ++i){
        if(smax[i - 1] > 0){
            pozmax[i] = pozmax[i - 1];
            smax[i] = v[i] + smax[i - 1];
        }
        else{
            pozmax[i] = i;
            smax[i] = v[i];
        }
        if(smin[i - 1] <= 0){
            pozmin[i] = pozmin[i - 1];
            smin[i] = v[i] + smin[i - 1];
        }
        else{
            pozmin[i] = i;
            smin[i] = v[i];
        }
    }

    smin[0] = 1e9;
    smax[0] = -1e9;

    for(int i = 1; i <= n; ++i){
        if(smax[i] > smax[pmax] or (smax[i] == smax[pmax] and pozmax[i] < pozmax[pmax]) or (smax[i] == smax[pmax] and pozmax[i] == pozmax[pmax] and i - pozmax[i] < pmax - pozmax[pmax])){
            pmax = i;
        }
        if(smin[i] < smin[pmin]){
            pmin = i;
        }
    }

    if(smax[pmax] > stotal - smin[pmin]){
        fout << smax[pmax] << ' ' << pozmax[pmax] << ' ' << pmax - pozmax[pmax] + 1;
    }
    else if(smax[pmax] < stotal - smin[pmin]){
        fout << stotal - smin[pmin] << ' ' << pmin + 1 << ' ' << n - (pmin - pozmin[pmin] + 1);
    }
    else{
        fout << smax[pmax] << ' ';
        if(pozmax[pmax] < pmin + 1){
            fout << pozmax[pmax] << ' ' << pmax - pozmax[pmax] + 1;
        }
        else if(pozmax[pmax] > pmin + 1){
            fout << pmin + 1 << ' ' << n - (pmin - pozmin[pmin] + 1);
        }
        else{
            fout << pmin + 1 << ' ' << min(pmax - pozmax[pmax] + 1, n - (pmin - pozmin[pmin] + 1));
        }
    }
}