Cod sursa(job #2397985)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 4 aprilie 2019 22:43:11
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("buline.in");
ofstream fout ("buline.out");

int n, c, nr, v[200001], d[200001], e[200001], suma, maxx, lsol, l, poz;

int main (){

      fin>>n;

      for(int i=1; i<=n; i++){
            fin>>nr;
            fin>>c;

            if(c == 0)
                  v[i]=-nr;
            else
                  v[i]=nr;

            suma=suma + v[i];
      }

      d[1]=v[1];

      maxx=d[1];
      lsol=1;
      l=1;
      poz=1;

      for(int i=2; i<=n; i++){

            if(d[i-1] + v[i] > v[i]){
                  d[i]=d[i-1] + v[i];
                  l++;
            }else{
                  l=1;
                  d[i]=v[i];
            }

            if(d[i] > maxx){
                  maxx=d[i];
                  lsol=l;
                  poz=i-l+1;
            }
      }

      e[1]=v[1];
      l=1;

      for(int i=2; i<=n; i++){

            if(e[i-1] + v[i] < v[i]){
                  e[i]=e[i-1] + v[i];
                  l++;
            }else{
                  e[i]=v[i];
                  l=1;
            }

            if(suma - e[i] > maxx){
                  maxx=suma - e[i];

                  if(i == n)
                        poz=1;
                  else
                        poz=i+1;

                  lsol=n-l;
            }
      }

      fout<<maxx<<" "<<poz<<" "<<lsol;


      return 0;
}