Cod sursa(job #2118336)

Utilizator lucametehauDart Monkey lucametehau Data 30 ianuarie 2018 15:22:59
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>

using namespace std;

ifstream cin ("buline.in");
ofstream cout ("buline.out");

const int MAX_N = 400000;

int Dq[1 + MAX_N];
int Sum[1 + MAX_N];

int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
    int X;
    bool tip;
    cin >> X >> tip;
    if(tip == 0)
      X = -X;
    Sum[i] = Sum[i + n] = X;
  }
  for(int i = 1; i <= 2 * n; i++)
    Sum[i] += Sum[i - 1];
  int Front = 1, Back = 0, sumMax = 0, l, r;
  for(int i = 1; i <= 2 * n; i++) {
    while(Front <= Back && Sum[i] <= Sum[Dq[Back]])
      Back--;
    Dq[++Back] = i;
    while(Front <= Back && i - Dq[Front] > n)
      Front++;
    if(sumMax < Sum[i] - Sum[Dq[Front]]) {
      sumMax = Sum[i] - Sum[Dq[Front]];
      l = Dq[Front] + 1;
      r = i;
    }
  }
  cout << sumMax << " " << l << " " << r - l + 1;
  return 0;
}