Submission #228338

#	Time	Username	Problem	Language	Result	Execution time	Memory
228338		quocnguyen1012	Hacker (BOI15_hac)	C++14	100 / 100	76 ms	22524 KiB

hac

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array
#define int long long

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 5;

int a[maxn], sum[maxn], N;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int tot = 0;
  cin >> N;
  for(int i = 1; i <= N; ++i){
    cin >> a[i];
    a[i + N] = a[i];
    tot += a[i];
  }
  for(int i = 1; i <= 2 * N; ++i){
    sum[i] = sum[i - 1] + a[i];
  }
  deque<ii> dq;
  int j;
  for(int i = 1; i <= N - N / 2 + 1; ++i){
    int v = sum[i + N / 2 - 1] - sum[i - 1];
    while(dq.size() && dq.back().fi < v) dq.pop_back();
    dq.eb(v, i);
    j = i;
  }
  int res = 0;
  for(int i = 1; i <= N; ++i){
    while(dq.size() && dq.front().se == i) dq.pop_front();
    res = max(res, tot - dq.front().fi);
    ++j;
    int v = sum[j + N / 2 - 1] - sum[j - 1];
    while(dq.size() && dq.back().fi < v) dq.pop_back();
    dq.eb(v, j);
  }
  cout << res;
}

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