Submission #990044

#	Time	Username	Problem	Language	Result	Execution time	Memory
990044		OAleksa	Hacker (BOI15_hac)	C++14	100 / 100	42 ms	25936 KiB

hac

#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 1e6 + 69;
int n, a[N], p[N], c[N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n;
  	for (int i = 1;i <= n;i++)
  		cin >> a[i];
  	for (int i = n + 1;i <= 2 * n;i++)
  		a[i] = a[i - n];
  	int all = 0;
  	for (int i = 1;i <= n;i++)
  		all += a[i];
  	for (int i = 1;i <= 2 * n;i++)
  		p[i] = p[i - 1] + a[i];
  	auto Get = [&](int l, int r) {
  		if (l > r)
  			return p[n] - p[l - 1] + p[r];
  		return p[r] - p[l - 1];
  	};
  	int k = (n + 1) / 2, ans = 0;
  	for (int i = 1;i <= n;i++) {
  		int j = i - k + 1;
  		if (j <= 0)
  			j += n;
  		c[i] = Get(j, i);
  	}
  	deque<pair<int, int>> st;
  	for (int i = n - k + 2;i <= n;i++) {
  		while (!st.empty() && st.back().s >= c[i])
  			st.pop_back();
  		st.push_back({i, c[i]});
  	}
  	for (int i = 1;i <= n;i++) {
  		while (!st.empty() && st.back().s >= c[i])
  			st.pop_back();
  		st.push_back({i, c[i]});
  		ans = max(ans, st.front().s);
  		int j = i - k + 1;
  		if (j <= 0)
  			j += n;
  		if (st.front().f == j)
  			st.pop_front();
  	}
  	cout << ans << '\n';
  }
  return 0; 
}

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