#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int, int> #define pb push_back #define ll long long #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define int long long using namespace std; template <typename t1, typename t2> bool maximize(t1 &a, const t2 &b){if(a < b){a = b; return 1;} else return 0;}; template <typename t1, typename t2> bool minimize(t1 &a, const t2 &b){if(a > b){a = b; return 1;} else return 0;}; void load(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if(fopen("test.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } } const int oo = 1e9 + 7; const ll OO = 1e18 + 7; const int maxn = 5e5 + 5; int n; int a[2 * maxn]; int pref[2 * maxn]; struct pp{ int val, id; }; deque<pp> dq; int k; int res = 0; void enter(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; a[i + n] = a[i]; } pref[0] = 0; for(int i = 1; i <= n * 2; i++){ pref[i] = pref[i - 1] + a[i]; } } int get_range(int l, int r){ return pref[r] - pref[l - 1]; } void add(int val, int id){ while(!dq.empty() && dq.back().val > val) dq.pop_back(); dq.push_back({val, id}); } void Try(){ k = (n + 1) / 2; for(int i = 1; i <= k; i++){ add(get_range(i, i + k - 1), i); } for(int i = k; i <= n + k - 1; i++){ while(dq.front().id <= i - k) dq.pop_front(); maximize(res, dq.front().val); // for(pp it : dq) cout << "{" << it.val << ", " << it.id << "} "; cout << '\n'; add(get_range(i + 1, i + k), i + 1); // cout << i << ' ' << res << ' ' << '\n'; } cout << res; } signed main(){ load(); enter(); Try(); cerr << '\n' << "Time ran: " << TIME << "s\n"; }

hac.cpp: In function 'void load()':
hac.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~