Cod sursa(job #2547856)

Utilizator Raresr14Rosca Rares Raresr14 Data 15 februarie 2020 19:35:45
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#define X first
#define Y second
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int i,n,v[200010],s[200010],x,y,poz,l,maxim,sol,p;
pair<int,int> D[200010];
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>x>>y;
        if(y==0){
            s[i]=s[i-1]-x;
            v[i]=-x;
        }else{
            s[i]=s[i-1]+x;
            v[i]=x;
        }
    }
    p=1;
    for(i=1;i<=n;i++){
        if(sol<0){
            sol=0;
            p=i;
        }
        sol+=v[i];
        if(sol>maxim){
            maxim=sol;
            poz=p;
            l=i-poz+1;
        }
    }
    for(i=1;i<=n;i++){
        if(D[i-1].X>s[i]){
            D[i]=D[i-1];
        }else{
            D[i].X=s[i];
            D[i].Y=i;
        }
    }
    for(i=1;i<=n;i++)
        if(maxim<D[i-1].X+s[n]-s[i-1]){
            maxim=D[i-1].X+s[n]-s[i-1];
            poz=i;
            l=n+D[i-1].Y-i+1;
        }
    fout<<maxim<<" "<<poz<<" "<<l;

    return 0;
}