Cod sursa(job #3165698)

Utilizator gabriel.9619Gabriel Stefan Tita gabriel.9619 Data 6 noiembrie 2023 19:12:45
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");

int v[200001], ss[200301];

int main()
{
    int n, s=0, t, smin=0, first, last, firstin, lastin, i1, i2, x, i, sinit=0;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i]>>t;
        if(t==0)
        {
            v[i]=-v[i];
        }
        sinit+=v[i];
    }
    s=0;
    ss[1]=v[1];
    i1=i2=1;
    for(i=2;i<=n;i++)
    {
        if(ss[i-1]+v[i]>=v[i])
        {
            ss[i]=ss[i-1]+v[i];
            i2=i;
        }
        else
        {
            ss[i]=v[i];
            i1=i2=i;
        }
        if(s<ss[i])
        {
            s=ss[i];
            first=i1;
            last=i2;
        }
    }
    smin=INT_MAX;
    ss[1]=v[1];
    i1=i2=1;
    for(i=2;i<=n;i++)
    {
        if(ss[i-1]+v[i]<=v[i])
        {
            ss[i]=ss[i-1]+v[i];
            i2=i;
        }
        else
        {
            ss[i]=v[i];
            i1=i2=i;
        }
        if(smin>ss[i])
        {
            smin=ss[i];
            firstin=i1;
            lastin=i2;
        }
    }
    smin=sinit-smin;
    if(s>=smin)
    {
        fout<<s<<" "<<first<<" "<<last-first+1;
    }
    else
    {
        fout<<smin<<" "<<lastin+1<<" "<<n-lastin+firstin-1;
    }
}