제출 #798208

#제출 시각아이디문제언어결과실행 시간메모리
798208tch1cherinHacker (BOI15_hac)C++17
100 / 100
101 ms11612 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(2 * N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i + N] = A[i];
  }
  int M = (N + 1) / 2;
  vector<int> B(2 * N);
  for (int i = 0; i < 2 * N; i++) {
    if (i > 0) {
      B[i] += B[i - 1];
    }
    B[i] += A[i];
    if (i >= M) {
      B[i] -= A[i - M];
    } 
  }
  int ans = 0;
  deque<int> dq;
  for (int i = 0; i <= 2 * N; i++) {
    while (!dq.empty() && B[dq.back()] >= B[i]) {
      dq.pop_back();
    }
    dq.push_back(i);
    if (dq.front() + M <= i) {
      dq.pop_front();
    }
    ans = max(ans, B[dq.front()]);
  }
  cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...