Cod sursa(job #2401023)

Utilizator alexradu04Radu Alexandru alexradu04 Data 9 aprilie 2019 12:51:10
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 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;
}