Cod sursa(job #2686025)

Utilizator Asgari_ArminArmin Asgari Asgari_Armin Data 18 decembrie 2020 12:55:48
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 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;
};

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 = 0; 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 = 0; i < n; ++i ){
    fin >> v[i] >> x;
    if( x == 0 )
      v[i] = -v[i];
    s += v[i];
  }
  lol val = ssm(n);
  for( i = 0; i < n; ++i )
    v[i] = -v[i];
  lol val2 = ssm(n);
  if( val.sum < s + val2.sum )
    fout << s + val2.sum << " " << val2.pos2 + 2 << " " << n - val2.pos2 + val2.pos1;
  else
    fout << val.sum << " " << val.pos1 + 1 << " " << val.pos2 - val.pos1 + 1;
  return 0;
}