Cod sursa(job #2686117)

Utilizator Asgari_ArminArmin Asgari Asgari_Armin Data 18 decembrie 2020 15:52:59
Problema Buline Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

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

const long long NMAX = 2e5;
long long v[NMAX + 1];

struct lol {
  long long pos1, pos2, sizes, sum;
  bool operator < ( const lol &var ) const {
    if( sum == var.sum ){
      if( pos1 == var.sum )
        return sizes < var.sizes;
      return pos2 < var.pos2;
    }
    return sum < var.sum;
  }
};

lol ssm( long long n ){
  long long s, stpoz, poz, maxx, cnt, solcnt, poz2;
  s = maxx = poz = 0;
  cnt = solcnt = 0;
  for( long long i = 1; i <= n; ++i ){
    s += v[i];
    ++cnt;
    if( s < 0 ){
      s = 0;
      poz = i + 1;
      cnt = 0;
    }
    if( maxx < s ){
      maxx = s;
      stpoz = poz;
      solcnt = cnt;
      poz2 = i;
    }
  }
  return {stpoz, poz2, solcnt, maxx};
}

int main() {
  long long n, i, s, x;
  fin >> n;
  s = 0;
  for( i = 1; i <= n; ++i ){
    fin >> v[i] >> x;
    if( x == 0 )
      v[i] = -v[i];
    s += v[i];
  }
  lol val = ssm(n);
  for( i = 1; i <= n; ++i )
    v[i] = -v[i];
  lol val2 = ssm(n);
  val2.sum += s; val.sizes = val.pos2 - val.pos1; val2.sizes = n - val2.pos2 + val2.pos1 - 1;
  val2.pos2 += 1;
  if( val < val2 )
    fout << val2.sum << " " << val2.pos2 << " " << val2.sizes;
  else
    fout << val.sum << " " << val.pos2 << " " << val.sizes;
  return 0;
}