Cod sursa(job #3275825)

Utilizator mihail_11Ionescu Mihail mihail_11 Data 11 februarie 2025 20:08:18
Problema Buline Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int t[400005];
deque<int> dqu;
int main()
{
    int n,val,semn,i,sum=0,smax=-2e9,start,lenght,fst,fln;
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>val>>semn;
        if(semn==0)
            val*=-1;
        t[i]=t[i+n+1]=val;
    }
    start=1;
    for(i=1;i<=2*n;++i)
    {
        dqu.push_front(t[i]);
        sum+=t[i];
        //cout<<start<<' '<<lenght<<'\n';
        if(sum<0)
        {
            dqu.clear();
            sum=0;
            start=i+1;
        }
        else
        {
            if(dqu.size()==n+1)
            {
                sum-=dqu.back();
                dqu.pop_back();
                ++start;
            }
            if(sum>smax)
            {
                smax=sum;
                fst=start;
                fln=dqu.size();
                //cout<<sum<<' '<<smax<<' '<<dqu.size()<<' '<<start<<' '<<"\n\n\n";
            }
        }
        //cout<<sum<<' '<<smax<<' '<<dqu.size()<<' '<<start<<' '<<"\n\n\n";
    }
    //cout<<start<<' '<<lenght<<'\n';
    fout<<smax<<' '<<fst<<' '<<fln-1;
    return 0;
}