Submission #284481

#	Time	Username	Problem	Language	Result	Execution time	Memory
284481		AlexLuchianov	Hacker (BOI15_hac)	C++14	100 / 100	94 ms	21756 KiB

hac

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <deque>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1000000;
ll v[1 + nmax], sum[1 + nmax];

std::deque<std::pair<int, ll>> dq;

void _insert(int k, ll number) {
  while(0 < dq.size() && number <= dq.back().second)
    dq.pop_back();
  dq.push_back({k, number});
}

void _clear(int lim) {
  while(dq.front().first <= lim)
    dq.pop_front();
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  for(int i = 1;i <= n; i++)
    std::cin >> v[i];
  int lim = (n + 1) / 2;
  for(int i = 1;i <= n; i++)
    v[n + i] = v[i];
  for(int i = 1;i <= 2 * n; i++)
    sum[i] = sum[i - 1] + v[i];
  
  for(int i = lim;i <= 2 * lim - 1; i++)
    _insert(i, sum[i] - sum[i - lim]);
  ll result = dq.front().second;
  for(int i = 2 * lim; i <= 2 * n; i++) {
    _insert(i, sum[i] - sum[i - lim]);
    _clear(i - lim);
    result = std::max(result, dq.front().second);
  }
  std::cout << result;
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40