Cod sursa(job #2547622)

Utilizator radugnnGone Radu Mihnea radugnn Data 15 februarie 2020 15:33:31
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int n,i,semn,s,sol,x,xx,y,lng;
int a[DIM],S[DIM];
pair <int,int> D[DIM];
int main(){
   fin>>n;
   for(i=1;i<=n;i++){
       fin>>a[i]>>semn;
       if(!semn)
        a[i]=-a[i];

       S[i]=S[i-1]+a[i];
       if(D[i-1].first > S[i]){
            D[i]=D[i-1];
       }
       else{
            D[i].first=S[i];
            D[i].second=i;
       }

   }
   for(i=1;i<=n;i++){
        if(s+a[i]>a[i])
            s+=a[i];
        else{
            s=a[i];
            x=i;
        }
        if(s>sol){
            sol=s;
            y=x;
            lng=i-x+1;
        }

   }
   for(i=1;i<=n;i++){
    if(D[i-1].first+S[n]-S[i-1] > sol){
        sol=D[i-1].first+S[n]-S[i-1];
        y=i;
        lng=n+D[i-1].second-i+1;
    }
   }
    fout<<sol<<" "<<y<<" "<<lng;
    return 0;
}