Cod sursa(job #3165522)

Utilizator Darius_CDarius Chitu Darius_C Data 6 noiembrie 2023 14:01:19
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>
#define DIM 10006
std::ifstream fin("buline.in");
std::ofstream fout("buline.out");
using namespace std;
typedef long long ll;

ll N, a[DIM];
ll total_sum;

void Read()
{
    total_sum=0;
    fin>>N;
    for(int val, semn, i=1;i<=N;i++) {
        fin>>val>>semn;
        total_sum += (a[i]=(semn==1 ? 1 : -1)*val);
    }
}

void Solve()
{
    /// cazul 1: nu trece prin mijloc, i.e. nu foloseste faptul ca sirul este circular
    ll smax=a[1];
    ll sum=a[1], st1=1, be_st1=1, be_dr1=1;
    for(int i=2;i<=N;i++) {
        if(sum<0)
            sum=0, st1=i;
        sum+=a[i];
        if(sum>smax)
            smax=sum, be_st1=st1, be_dr1=i;
        else if(sum==smax) {
            if(st1 < be_st1 || (st1 == be_st1 && i < be_dr1))
                be_st1=st1, be_dr1=i;
        }
    }

    /// cazul 2: trece prin mijloc, i.e. este de forma
    /**
    [st2 ... n-1 n 1 2 ... dr2] = suma maxima
    = [1 ... n] - [st2+1 ... dr2-1] = suma maxima
       s fixa
    deci [st2 ... dr2] = suma minima, secventa care nu trece prin mijloc , deci necircular
    */
    ll smin=a[1];
    sum=a[1]; ll st2=1, be_st2=1, be_dr2=1;
    for(int i=2;i<=N;i++) {
        if(sum>0)
            sum=0, st2=i;
        sum+=a[i];
        if(sum<smin)
            smin=sum, be_st2=st2, be_dr2=i;
        else if(sum==smin) {
            if(st2 < be_st2 || (st1 == be_st1 && i > be_dr2))
                be_st2=st2, be_dr2=i;
        }
    }
    ll circmax = total_sum - smin;

    /// comparam si dam raspuns
    ll P1=be_st1, L1 = be_dr1-be_st1+1;
    ll P2=be_st2+1, L2 = N - (be_dr2-be_st2+1);

    ll best, Pb, Lb;
    if(smax > circmax) best=smax, Pb=P1, Lb=L1;
    else if(circmax > smax) best=circmax, Pb=P2, Lb=L2;
    else {
        best=smax;
        if(P1 < P2) Pb=P1, Lb=L1;
        else if(P2 < P1) Pb=P2, Lb=L2;
        else {
            Pb=P1;
            if(L1 < L2) Lb=L1;
            else if(L2 < L1) Lb=L2;
            else Lb=L1;
        }
    }
    fout<<best<<" "<<Pb<<" "<<Lb;
}

int main()
{
    Read();
    Solve();
    return 0;
}