# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1205937 | CrabCNH | Hacker (BOI15_hac) | C++20 | 113 ms | 90456 KiB |
#include <bits/stdc++.h>
#define task "BriantheCrab"
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define szf sizeof
#define sz(s) (int)((s).size())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}
const int maxN = 5e5 + 5;
const int maxlg = 20;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
int a[maxN], pfs[maxN], lg[maxN];
int st[maxN][maxlg];
int get (int l, int r) {
int k = lg[r - l + 1];
return min (st[l][k], st[r - (1 << k) + 1][k]);
}
void solve () {
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
a[n + i] = a[i];
}
for (int i = 1; i <= n * 2; i ++) {
pfs[i] = pfs[i - 1] + a[i];
}
for (int i = 2; i < maxN; i ++) {
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i <= n * 2; i ++) {
st[i][0] = pfs[i + (n + 1) / 2 - 1] - pfs[i - 1];
}
for (int l = 1; l <= lg[n * 2]; l ++) {
for (int i = 1; i + (1 << l) - 1 <= n * 2; i ++) {
st[i][l] = min (st[i][l - 1], st[i + (1 << (l - 1))][l - 1]);
}
}
int res = 0;
for (int i = (n + 1) / 2; i <= n * 2; i ++) {
maximize (res, get (i - (n + 1) / 2 + 1, i));
}
cout << res;
return;
}
signed main () {
cin.tie (nullptr) -> sync_with_stdio (false);
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
int t = 1;
//cin >> t;
while (t --) {
solve ();
}
return 0;
}
// thfv
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |