Cod sursa(job #2929724)

Utilizator Utucora2017Nicolae Utucora2017 Data 26 octombrie 2022 18:33:34
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
using namespace std;
ifstream cin("buline.in");
ofstream cout("buline.out");
int v[200005];
int n,sc,summax,stmax,drmax,culoare,lmax,smin,drmin,stmin,s=0,summax2,stmax2,lmax2,drmax2;
int main(){
    int x,st=0,dr=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>culoare;
        if(culoare==0)
            v[i]=-x;
        else
            v[i]=x;
        s=s+v[i];
    }
    sc=summax=v[1];
    st=stmax=drmax=1;
    for(dr=2;dr<=n;dr++){
        if(sc+v[dr]>=v[dr])
            sc=sc+v[dr];
        else{
            sc=v[dr],st=dr;
        }
        if(sc>summax)
        {
            summax=sc;
            stmax=st;
            drmax=dr;
        }
    }
    lmax=drmax-stmax+1;
    sc=smin=v[1];
    st=stmin=drmin=1;
    for(dr=2;dr<=n;dr++){
        if(sc+v[dr]<v[dr])
            sc=sc+v[dr];
        else{
            sc=v[dr];
            st=dr;
        }
        if(sc<smin){
            smin=sc,stmin=st,drmin=dr;
        }
    }
    summax2=s-smin;
    stmax2=drmin+1;
    drmax2=stmin-1;
    lmax2=drmax2+n-stmax2+1;
    if(summax>summax2)
        cout<<summax<<" "<<stmax<<" "<<lmax;
    else
        cout<<summax2<<" "<<stmax2<<" "<<lmax2;
}