Submission #1185790

#TimeUsernameProblemLanguageResultExecution timeMemory
1185790Rokas159Hacker (BOI15_hac)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int MAXN = 4+2; int l[2*MAXN], r[2*MAXN], val[2*MAXN]; int sums[MAXN]; int n; int currInd = 0; void build(int v = 1) { if (v < n) { build(v*2); build(v*2+1); l[v] = l[v*2]; r[v] = r[v*2+1]; val[v] = min(val[v*2], val[v*2+1]); } else { l[v] = currInd; r[v] = currInd; val[v] = sums[currInd++]; } } int query(int L, int R, int v = 1) { if (R < l[v] || r[v] < L) { return INT32_MAX; } else if (L <= l[v] && r[v] <= R) { return val[v]; } else { return min(query(L, R, v*2), query(L, R, v*2+1)); } } signed main() { cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false); cin >> n; int a[n]; int sum = 0; int half = (n+1)/2; for (int i = 0; i < n; i++) { cin >> a[i]; if (i < half) { sum += a[i]; } } for (int i = 0; i <= n; i++) { sums[i%n] = sum; sum += a[(i+half)%n]; sum -= a[i%n]; } build(); int ans = 0; for (int i = 0; i < n; i++) { int L = (i-half+1 +n)%n; int R = i; if (R < L) { ans = max(ans, min(query(0, R), query(L, n-1))); } else { ans = max(ans, query(L, R)); } } cout << ans << endl; cout.flush(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...