Cod sursa(job #2923949)

Utilizator AztecaVlad Tutunaru 2 Azteca Data 21 septembrie 2022 18:11:37
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>

using ll = long long;

const int MAX_N = 200000;

int a[2 * MAX_N + 1];
ll sp[2 * MAX_N + 1];
std::deque<int> dq;

void update(ll &sum, int &pos, int &len, int sum_, int pos_, int len_) {
  if (sum < sum_) {
    sum = sum_;
    pos = pos_;
    len = len_;
  } else if (sum == sum_ && pos_ < pos) {
    pos = pos_;
    len = len_;
  } else if (sum == sum_ && pos_ == pos && len_ < len) {
    len = len_;
  }
}

void insert(int i) {
  while (!dq.empty() && sp[i] < sp[dq.back()]) {
    dq.pop_back();
  }
  dq.push_back(i);
}

int main() {
  std::ifstream fin("buline.in");
  std::ofstream fout("buline.out");
  int n;
  fin >> n;
  for (int i = 1; i <= n; i++) {
    int t;
    fin >> a[i] >> t;
    if (t == 0) {
      a[i] *= -1;
    }
  }
  for (int i = n + 1; i <= 2 * n; i++) {
    a[i] = a[i - n];
  }
  for (int i = 1; i <= 2 * n; i++) {
    sp[i] = sp[i - 1] + a[i];
  }
  ll sum = 0;
  int pos = (1 << 30), len = (1 << 30);
  dq.push_back(0);
  for (int i = 1; i <= n; i++) {
    update(sum, pos, len, sp[i] - sp[dq.front()], dq.front() + 1, i - dq.front());
    insert(i);
  }
  for (int i = n + 1; i <= 2 * n; i++) {
    if (dq.front() == i - n - 1) {
      dq.pop_front();
    }
    update(sum, pos, len, sp[i] - sp[dq.front()], dq.front() + 1, i - dq.front());
    insert(i);
  }
  fout << sum << " " << pos << " " << len;
  return 0;
}