Cod sursa(job #2931553)

Utilizator AlmaChan13Petria Mitran Alma Elena AlmaChan13 Data 31 octombrie 2022 14:50:15
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,i,val,v[400100],st[400100],sum[400100],s[400100],sumax[400100],Lsol,isol,sol;
int main () {
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>v[i]>>val;
        if (val==0) {
            v[i]=-v[i];
        }
        if (s[i-1]+v[i]>v[i]) {
            s[i]=s[i-1]+v[i];
            st[i]=st[i-1];
        }
        else {
            s[i]=v[i];
            st[i]=i;
        }
        if (s[i]>sol) {
            sol=s[i];
            isol=st[i];
            Lsol=i-st[i]+1;
        }
    }
    sum[1]=v[1];
    sumax[1]=v[1];
    for (i=2;i<=n;i++) {
        sum[i]=sum[i-1]+v[i];
        sumax[i]=max(sumax[i-1],sum[i]);
        if (sumax[i-1]>sum[i]) {
            sumax[i]=sumax[i-1];
            st[i]=st[i-1];
        }
        else {
            sumax[i]=sum[i];
            st[i]=i;
        }
    }
    for (i=1;i<=n;i++) {
        if (sol<sumax[i-1]-sum[n]+sum[i-1]) {
            sol=sumax[i-1]-sum[n]+sum[i-1];
            isol=i;
            Lsol=st[i-1]+n-i+1;
        }
    }
    fout<<sol<<" "<<isol<<" "<<Lsol;
}