Cod sursa(job #1379462)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 6 martie 2015 17:59:37
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <fstream>
#define DIM 200010
using namespace std;

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

int n, i, j, v[DIM], sum, x, y, maxim;
int bmin[3][DIM], bmax[3][DIM], start;
int length;

void SetUp(){
     fin >> n;
     for(i = 1; i <= n; i ++){
          fin >> x >> y;
          if(y == 1) v[i] = +x;
          if(y == 0) v[i] = -x;
          sum += v[i];
     }
     return;
}

void SSMax(){
     for(i = 1; i <= n; i ++){
          if(bmax[1][i-1] + v[i] > v[i]){
               bmax[1][i] = bmax[1][i-1] + v[i];
               bmax[2][i] = bmax[2][i-1] + 1;
          }
          else{
               bmax[1][i] = v[i];
               bmax[2][i] = 1;
          }
          if(maxim < bmax[1][i]){
               maxim = bmax[1][i];
               start = i - bmax[2][i] + 1;
               length= bmax[2][i];
          }
          else{
               if(maxim == bmax[1][i]){
                    if(start > i - bmax[2][i] + 1){
                         maxim = bmax[1][i];
                         start = i - bmax[2][i] + 1;
                         length= bmax[2][i];
                    }
                    else{
                         if(start == i - bmax[2][i] + 1){
                              if(length > bmax[2][i]){
                                   maxim = bmax[1][i];
                                   start = i - bmax[2][i] + 1;
                                   length= bmax[2][i];
                              }
                         }
                    }
               }
          }
     }
     return;
}

void SSMin(){
     for(i = 1; i <= n; i ++){
          if(bmin[1][i-1] + v[i] <= v[i]){
               bmin[1][i] = bmin[1][i-1] + v[i];
               bmin[2][i] = bmin[2][i-1] + 1;
          }
          else{
               bmin[1][i] = v[i];
               bmin[2][i] = 1;
          }
          if(maxim < sum - bmin[1][i]){
               maxim =  sum - bmin[1][i];
               start = i + 1;
               length = n - bmin[2][i];
          }
          else{
               if(maxim == sum - bmin[1][i]){
                    if(start > i + 1){
                         maxim =  sum - bmin[1][i];
                         start = i + 1;
                         length = n - bmin[2][i];
                    }
                    else{
                         if(length > n - bmin[2][i]){
                              maxim =  sum - bmin[1][i];
                              start = i + 1;
                              length = n - bmin[2][i];
                         }
                    }
               }
          }
     }
     return;
}

void Finish(){
     fout << maxim << " ";
     fout << start << " ";
     fout << length<< " ";
     return;
}

int main(){
     SetUp();
     SSMax();
     SSMin();
     Finish();
     return 0;
}